Giga-xor

An interval $[a, b]$ is a giga-xor interval if and only if the xor sum of the natural numbers inside the interval $[a, b]$ is equal to $0$, where $a$ and $b$ are natural numbers.

Strictly speaking, an interval $[a, b]$ is giga-xor if and only if $a ⊕ (a + 1) ⊕ (a + 2) ⊕ ... ⊕ b = 0$.

You are given $T$ pairs of numbers $(a, b)$. For each pair, you need to find the length of the shortest interval $[x, y]$ such that $1 \le x \le a \le b \le y$ and $[x, y]$ is a giga-xor interval.

Input

The first line contains $T$ ($1 ≤ T ≤ 5 \cdot 10^5$), the number of pairs.

On the following $T$ lines, there are $2$ integers $a$, $b$ ($1 ≤ a ≤ b ≤ 10^{18}$).

For tests worth $10$ points, $b ≤ 100$

For tests worth $30$ more points, $b ≤ 10^6$

Output

Print on $T$ lines, the answer for each pair.

Example

stdin

5	
4 5
2 3
1 7
8 8
1 10

stdout

4
3
7
4
11