beecrowd | 1926

Marianne and The Twin Cousins

By Gustavo Ribeiro, IFPB - Campina Grande BR Brazil

Timelimit: 1

Marianne is programming her own game called “Hero of the Guitar” . It’s a extremely tiresome work, that needs a lot of time and effort, but nothing that some free time doesn't solves. Someday she received an e-mail, in the e-mail Mari has encountered a very curious problem proposed by the cousins Renè and Leonhard and the twins Isaac and Carl.

The problem is described as the following:

“A natural number is prime, if it’s divided by exactly two numbers: number one and it self (one isn't prime). A number is twin prime, if and only if, it’s prime and there is another prime number b, such that |a - b| = 2. An example: number 3 is twin prime, because it’s prime and there’s another prime (5) with |3 - 5| = 2. But number 23, despite being a prime number, isn't twin prime. Could you tell me how much twin primes there is between two numbers x and y?”

Marianne loves to solve this kind of problem, but she is busy programming her game. Could you help her?

Input

In the first line there is an integer 1 ≤ Q ≤ 105, the number of querys, each of the next Q lines will have two numbers, 1 ≤ X, Y ≤ 106.

Output

For each query Q, print the quantity of twin primes between X and Y, inclusive.

Input Samples Output Samples

3

1 7

5 7

8 12

3

2

1

2

1 10

1 100

3

15