L. Chance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After Noura's brother, Tamim, finished his junior training, coach Fegla was impressed with his progress. He told Noura that if Tamim would solve the following problem in SCPC2015 and yet does not qualify to the ACPC2015, he will give him a chance to participate unofficially in it.

The problem goes as follows:

Given L and R, how many integers between them have a prime number of ones in their binary representation?

Can you help Tamim participate in the ACPC2015?

Input

The first line of input contains an integer T (1 ≤ T ≤ 105), the number of test cases.

Each test case will consist of two space - separated integers: L and R (0 ≤ L ≤ R ≤ 105).

Output

For each test case, print the number of integers between L and R that have a prime number of ones in their binary representation.

Examples
Input
3
2 10
1 19
3 101
Output
6
13
65
Note

Warning: large Input/Output data, be careful with certain languages.