题目描述

给定两个正整数 $l$ 和 $r$（保证 $l \leq r$），求 $l \leq x < y \leq r$ 时 $gcd(x, y)$ 的最大值。

其中 $gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数，即 $gcd(x,y) = max_{x\%d = y \% d = 0} d$ 。

输入格式

输入多行。

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个正整数 $l$ 和 $r$ 表示一组询问。

输出格式

输出多行。

一共 $T$ 行，每行两个正整数表示答案。

样例 #1

样例输入 #1

10
1 100
35 85
16 30
8 78
33 72
1 2
9 69
1 33
20 29
9 99

样例输出 #1

50
42
10
39
36
1
34
16
7
49

提示

【样例解释】：

【样例 $1$ 解释】

对于，$l=1，r=100$，显然当，$x=50，y=100$ 时能取得最大的 $gcd(x,y) = 50$ 。

【样例 $2$ 解释】

见目录 $2.in/2.ans$

本样例符合测试点编号为 $2$ 的数据范围。

【样例 $3$ 解释】

见目录 $3.in/3.ans$

本样例符合测试点编号为 $3$ 的数据范围。

【样例 $4$ 解释】

见目录 $4.in/4.ans$

本样例符合测试点编号为 $4$ 的数据范围。

【样例 $5$ 解释】

见目录 $5.in/5.ans$

本样例符合测试点编号为 $5$ 的数据范围。

【数据范围】：

对于 $100\%$ 的数据保证 $1 \leq T \leq 100, 1 \leq l < r \leq 10^{11}$ 。