On the Sea

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

Input	Output
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$.