Tsunami waves do not resemble normal undersea currents or sea waves, because their wavelength is far longer. In a far distant island, a tribesman is studying these waves to save his people from future Tsunamis. He is able to solve all scientific calculations but is weak with prime numbers. Help him to complete his research.
You are given Q queries and in each query you have to answer number of numbers between l and r such that number of set bits in binary representation of the number is a prime number.
NOTE : Describing a bit as being set or clear is just another way of saying that the bit has the value 1(set) or 0(clear).
Input :
First line of input is Q representing total number of queries.
Next Q line have two integers representing l and r.
Output :
Print Q lines each representing answer to query.
Constraints :
1 <= Q <= 103
1 <= l <= r <= 1018
Binary representation of 1-5 are {1, 10, 11, 100, 101} and number of set bits are {1, 1, 2, 1, 2 } respectively. Out of all these numbers only 3 and 5 have prime number of set bits.
