By Gustavo Ribeiro, IFPB - Campina Grande Brazil
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?
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.
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 |