Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

On the Sea

By YouKnowWho · Limits 2s, 512 MB

Cherry isn't feeling well right now as she found a problem that she couldn't solve. So she started to listen to On the Sea and you, to make her happy, have to solve the problem for her.

For any non-negative integer nn, let f(n)f(n) be the median of the submasks of nn.

You are given two integers ll and rr. You have to find the median of the sequence f(l),f(l+1),,f(r)f(l), f(l + 1), \ldots, f(r).

An integer xx is a submask of yy if xx can be obtained by replacing some (possibly none or all) 11-s in the binary representation of yy by 00-s.

The median of a sequence is the value of an element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used. For example, the median of [4,2,7,5][4,2,7,5] is 44 since after sorting the sequence, it will look like $[2,4,5,7]$ and the left of two middle elements is equal to 44. The median of [7,1,2,9,6][7,1,2,9,6] equals 66since after sorting, the value 66 will be in the middle of the sequence.

Input

The first line of the input contains a single integer t(1t105)t(1 \le t \le 10^5) denoting the number of test cases. The description of tt test cases follows.

The first and only line of each test case contains two space-separated integers ll and rr (1lr109)(1 \le l \le r \le 10^9).

Output

For each test case, print a single line containing the median of the of the sequence f(l),f(l+1),,f(r)f(l), f(l + 1), \ldots, f(r).

Sample

InputOutput
3
1 5
7 10
696969 69696969
0
1
8073418

In the second test case,

The sorted list of the submasks of 77 is [0,1,2,3,4,5,6,7][0, 1, 2, 3, 4, 5, 6, 7], so f(7)=3f(7) = 3 .
The sorted list of the submasks of 88 is [0,8][0, 8], so f(8)=0f(8) = 0.
The sorted list of the submasks of 99 is [0,1,8,9][0, 1, 8, 9], so f(9)=1f(9) = 1.
The sorted list of the submasks of 1010 is [0,2,8,10][0, 2, 8, 10], so f(10)=2f(10) = 2.

So we have to find the median of the sequence f(7),f(8),f(9),f(10)f(7), f(8), f(9), f(10), and the list of these values is [3,0,1,2][3, 0, 1, 2], and finally, the median of this list is 11.


    Discussion

    Statistics


    92% Solution Ratio

    Ashiqur.141492Earliest, 9M ago

    adnan_tokyFastest, 0.1s

    Ashiqur.141492Lightest, 1.0 MB

    TasdidShortest, 760B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.