403237: GYM101086 I Home Sweet Home

While Coach Fegla and Noura were flying back home from Marrakech after attending the ICPC2015 World Finals, they got really bored in their 6 - hour plane trip, so the coach decided to tell Noura some cool information about binary numbers and operators, and he gave her this challenge to pass the time.

Coach Fegla asked her if she could find the number of ways to choose two integers, A and B, such that (L ≤ A, B ≤ R) and the XOR of the binary representations of A and B (without leading zeros) is palindrome in binary.

For example, , after removing leading zeros 101 is palindrome.

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

Each test case will contain two space - separated integers L, R (0 ≤ L ≤ R ≤ 10¹²).

For each test case print the number of ways on a single line.

3
1 4
0 0
4 8

12
1
15

A string of binary digits is a palindrome if it can be read the same from either direction.

For example: 0, 11 and 10101 are palindromes, while 10 and 10011 are not.

means XOR, remember that:

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