H. Shoree hates Moon's EX (Mint)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Shoree is Moon's friend, she loves math, especially phi $$$\varphi$$$, the euler totient function, Shoree decided to make her own function called the Shoree function, defined as

$$$shoree(x) = \varphi(x)$$$ $$$XOR$$$ $$$x$$$

Given $$$l$$$ and $$$r$$$, find

$$$\operatorname{MEX}$$$($$$shoree(l), shoree(l+1), ..., shoree(r)$$$)
Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — denotes the number of test cases.

The first line and only of each test case contain two integers $$$l, r$$$ $$$(1 \le l \le r \le 10^9)$$$ — denotes the number of queries and the left boundary and the right boundary of the sum of the function respectively.

Output

for each test case, print $$$\operatorname{MEX}$$$($$$shoree(l), shoree(l+1), ..., shoree(r)$$$)

Example
Input
3
2 3
1 1
1 7
Output
0
1
2
Note

$$$\varphi(x)$$$ is defined as Euler's totient function counts the positive integers up to a given integer $$$n$$$ that are relatively prime to $$$n$$$,

Note that $$$\varphi(1)$$$ $$$=$$$ $$$1$$$

For example $$$\varphi(9) = 6$$$ because the six numbers $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$, $$$7$$$ and $$$8$$$ are all the numbers that are from $$$1$$$ to $$$9$$$ and are relatively prime to $$$9$$$

The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$