Mr Foolizm is learning binary numbers. He has a software that converts any decimal integer to binary and vice versa. So, if he is asked to add some decimal numbers, he first converts them to binary. Then he adds them in binary. But he doesn't understand the carry principle yet and he even doesn't know the idea of positioning the numbers. Instead of LSD (least significant digit), he starts summing from MSD (most significant digit). So, if he is asked to add four integers from 1 to 4, he does the following:

1. He first takes 1 and 2 and convert them to binary using his software, and then he adds them like the following:

    1
    10
    __
    00

2. Then he takes 3, converts it to binary and adds it with the previous result:

    00
    11
    __
    11

3. He then takes 4, converts it to binary and adds it with the previous result:

    11
    100
    ___
    010

4. And finally he converts the result back to decimal, so, the result is 2.

Now you are given two integers p and q, your task is to find the result if Mr Foolizm adds all integers from p to q (inclusive) in his procedure.

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing two integers: p and q (0 < p < q < 2⁶³).

For each case, print the case number and the result.