Bob has just learned number theory and is very excited about it. Unlike everytime, Bob is not in trouble this time, but being kind hearted he now goes to his friend Peter who is stuck at a problem of Number theory, to help him. Now, Peter describes the problem to Bob as, given two numbers a and b(both inclusive), find the number of prime pairs between a and b whose XOR is an odd number. Bob thinks for a while and then looks at the constraints of a and b. As he finds that the constraints are large enough that can't be handled manually, he asks your help to write a program for the same.

Input:

The first line consists of the number of test cases t. t lines follow then.
Each of the t lines, consists of 2 positive integers a and b, separated by a space.

Output:

For each test case, output the desired result on a separate line.

Constraints:

1 ≤ t ≤ 10

1 ≤ a, b ≤ 10^9

0 ≤ b-a ≤ 10^6

SAMPLE INPUT
1
2 4

SAMPLE OUTPUT
1

Explanation

Between 2 and 4, numbers that are prime are 2, 3. The prime number pair whose XOR is odd is: (2, 3)

见题面

见题面