403240: GYM101086 L Chance

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?

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

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

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

3
2 10
1 19
3 101

6
13
65

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