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