The Clash of Tactical Titans: Klopp vs. Ten Hag

In the intense world of football rivalries, where victory and defeat carry immense weight, two iconic tacticians have emerged as the focal points of a legendary showdown: Jürgen "Prime Dominator" Klopp, the unyielding coach of Liverpool FC, and Erik "Prime Struggler" ten Hag, the enigmatic leader of Manchester United. Their rivalry centers around a peculiar belief - the influence of prime numbers on the outcome of matches.

Part 1: Klopp's Legendary Belief

Coach Klopp, revered for his charismatic leadership and dynamic playing style, has an unshakable belief in the concept of Prime Victory Blitz Days. According to Klopp, these are extraordinary dates when both the day and the month are prime numbers, destined to bring triumph to Liverpool FC. Klopp's relentless pursuit is to find these dates, as he believes they are the key to Liverpool's unparalleled success.

Part 2: Ten Hag's Troubles

On the opposing side, Coach Ten Hag, celebrated for his tactical prowess, has been burdened by an unusual belief in what he dubs "Prime Defeat Days." Ten Hag is convinced that on dates where both the day and the month are prime numbers, Manchester United is destined to face defeat. He is on a mission to avoid these days at all costs, for he believes they spell doom for his team.

Part 3: The Fateful Encounter

As fate would have it, both coaches have circled a significant date on their calendars: 05/03/2023. On this day, Liverpool FC is set to square off against Manchester United in a high-stakes, international club competition. For Klopp, it's a Prime Victory Blitz Day, while for Ten Hag, it's a dreaded Prime Defeat Day.

Part 4: The Clash on 05/03/2023

The football world is abuzz with anticipation as Klopp and Ten Hag face off on 05/03/2023. It's a match for the ages, filled with tension, drama, and extraordinary moments. As the clock ticks, both teams give their all, and the outcome remains uncertain until the final whistle.

Part 5: The Outcome

The match ends in a spectacular 7-0, leaving fans in awe of the display of skill and tactics. Klopp celebrates what he calls another Prime Victory Blitz Day, while Ten Hag breathes a sigh of frustration!

Part 6: The Continuing Rivalry

The rivalry between Klopp and Ten Hag continues, each coach seeking to prove their theory about prime numbers. Klopp hunts for Prime Victory Blitz Days to cement Liverpool's dominance, while Ten Hag strategizes to avoid Prime Defeat Days and lead Manchester United to victory.

Write a program that assists Klopp and Ten Hag in their quest to identify Prime Victory Blitz Days and Prime Defeat Days for their respective teams. Your task is to calculate the total count of these special dates within a given range of years, as both coaches aim to shape the destiny of their teams.

Input

The first line comprises an integer, $T$ $(1 \leq T \leq 20100)$, representing the number of test cases.

For each test case there are two positive integers: the starting year $s$, and the ending year $e$, where$10^{2}\leq s\leq e \leq 10^{12}$.

Output

An integer representing the count of Prime Victory Blitz Days for Liverpool FC within the given range.

Sample

Input	Output
2 1900 1902 2022 2023	156 104