Time Limit: 1000 MS Memory Limit: 65536 K

## Description

we define a function f( x ) = the number of 1 in the binary sequene of (x ^ x + 1).
now I want to know the value of f(a) + f(a + 1 ) + ... + f(b). can you tell me ?
## Input

The first line of input is the number of test case.
For each test case, there is one lines contains two numbers a, b ( 0 <= a <= b <= 10^9 ).
## Output

For each test case output the answer on a single line,
## Sample Input

3
1 10
3 33
4 44
## Sample Output

18
62
79
## Source

onmylove@scuacm
Sichuan University Programming Contest 2012 Final