A positive integer is said to be bitwise prime if the sum of all the bits in its binary representation is a prime number. 

You are given two integers a and b. You have to output number of bitwise prime numbers between a and b (inclusive).

Input

First line contains T : number of test cases. (1 ≤ T ≤ 10⁵)

For next T lines, each test case contains two space separated integers a and b. (a ≤ b). 1 ≤ a, b ≤ 10¹⁹.

Output

For each test case, print the number of bitwise prime numbers between a and b (inclusive).

Example

Input:
2
1 2
1 3
Output:
0
1