One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B in 2's complement representation using 32 bits. How many 1's will you write down in all?

Input

The first line contains the number of test cases T. Each of the next T lines contains two integers A and B.

Output

Output T lines, one corresponding to each test case.

Constraints:

-2³¹ <= A <= B <= 2³¹ - 1

Sample

Input:
3
-2 0
-3 4
-1 4

Output:
63
99
37

Explanation

For the first case, -2 contains 31 1's followed by a 0 whereas -1 contains 32 1's. Thus the total is 63.

For the second case, the answer is 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99