Menji likes greatest common divisors, especially pairs of positive integers with a large greatest common divisor.

Let $\gcd(x,y)$ denote the greatest common divisor of $x$ and $y$. Given multiple pairs of $L$ and $R$ where $L < R$ is guaranteed, find $\max\limits_{L\leq x < y\leq R}\gcd(x,y)$.

Input

The input is read from standard input.

The first line contains a positive integer $T$ ($1\leq T\leq 10$), representing the number of test cases.

Each of the following $T$ lines contains two positive integers $L$ and $R$ ($1\leq L < R\leq 10^{12}$), representing a query.

Output

The output is written to standard output.

For each query $L, R$, output a single positive integer representing $\max\limits_{L\leq x < y\leq R}\gcd(x,y)$ on a new line.

Examples

Input 1

10
1 2
2 4
6 10
11 21
147 154
1470 1540
2890 3028
998244353 1000000007
34827364537 41029384775
147147147147 154154154154

Output 1

1
2
3
7
7
70
126
1754385
5861340682
7007007007