We consider the sequence made up as follows:
- initially, the sequence is "1";
- at every step, the following transformations occur on the sequence: "1" -> "10" and "0" -> "1".
After an infinite number of applying these transformations we get sequence "1011010110110101101...".
A total of Q questions are asked, which sound like this: How many 1s are in the sequence between positions a and b ?

Line one of input file infinit.in contains number Q. The following Q lines each contain a pair of numbers a, b, each separated by a space.

File infinit.out will contain Q lines, with line i containing the answer for pair (a, b) of the (i+1)-th line of the input file.

• 1 <= Q <= 5000
• 1 <= a <= b < 2⁶³
  

infinit.in	infinit.out
1 2 8	4

Time limit: 0.1 seconds/test

Tiberiu-Lucian Florea
University of Bucharest, Mathematics & IT Department
Contact: tiberiu.florea@gmail.com