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 $n$, let $f(n)$ be the median of the submasks of $n$.

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

An integer $x$ is a submask of $y$ if $x$ can be obtained by replacing some (possibly none or all) $1$-s in the binary representation of $y$ by $0$-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]$ is $4$ since after sorting the sequence, it will look like $[2,4,5,7]$and the left of two middle elements is equal to $4$. The median of $[7,1,2,9,6]$ equals $6$since after sorting, the value $6$ will be in the middle of the sequence.

Input

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

The first and only line of each test case contains two space-separated integers $l$ and $r$ $(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), \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 $7$ is $[0, 1, 2, 3, 4, 5, 6, 7]$, so $f(7) = 3$ .
The sorted list of the submasks of $8$ is $[0, 8]$, so $f(8) = 0$.
The sorted list of the submasks of $9$ is $[0, 1, 8, 9]$, so $f(9) = 1$.
The sorted list of the submasks of $10$ is $[0, 2, 8, 10]$, so $f(10) = 2$.

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


    Discussion

    Statistics


    92% Solution Ratio

    Ashiqur.141492Earliest, 1M ago

    adnan_tokyFastest, 0.1s

    Ashiqur.141492Lightest, 1.0 MB

    TasdidShortest, 760B

    Submit

    Login to submit