This problem is from MIUP'2023.

[PC037] This is the way

You have just arrived at planet Numberlore. While ordering 2 space beers from the Fibonacci bar, the bartender was quick to tell you should instead ask for 10 beers. "Always use binary numbers. This is the way!".

Later, when entering the hotel 10101, you found out numberlorians are very superstitious. In fact, this hotel had only 14 rooms, all corresponding to numbers that in binary have more ones (digit 1) than zeros (digit 0). In parenthesis is the corresponding number in decimal:

These ten numbers are all the binary numbers smaller or equal than 25 in which the quantity of ones is strictly larger than the quantity of zeros. However, there are many other such numbers bigger than 25, such as 11010 (26) or 101101 (45).

You could not stop thinking about this in your decimal mind, wandering how many such numbers were there for any given range.

Task

Given two integers \(a\) and \(b\) (in decimal base), your task is to compute the amount of numbers in the range \([a,b]\) (inclusive) that have more ones than zeros in their binary representation.

Input

The first line contains an integer \(N\), indicating the amount of test cases that follow.

Each of the following \(N\) lines contains two integers \(a\) \(b\) defining a range for which you need to compute the desired quantity.

Output

The output should contain \(N\) lines, each one indicating the amount of numbers in the respective range that have more ones than zeroes in their binary representation.

Constraints

5
1 25
10 100
41 42
999 999
1234 5678

14
48
0
1
2258

Explanation of example

• There are 14 numbers in the range [1,25] that have more ones than zeroes in their binary representation (the numbers given in the problem statement for the 10101 hotel)
• There are 48 such numbers in the range [10,100]
• There are no such numbers in the range [41,42]
• There is 1 such number in the range [999,999]
• There are 2258 such numbers in the range [1234,5678]