403240: GYM101086 L Chance
Description
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?
InputThe 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).
OutputFor each test case, print the number of integers between L and R that have a prime number of ones in their binary representation.
ExamplesInput3Output
2 10
1 19
3 101
6Note
13
65
Warning: large Input/Output data, be careful with certain languages.