最大公因数

gcd

• 时间限制：2.0 秒
• 内存限制：512 MiB
• 输入输出：标准输入输出

题目描述

给定两个正整数 $l, r$（保证 $l < r$），求 $\max_{l \le x < y \le r} \gcd(x, y)$。

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

输入格式

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

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

输出格式

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

样例 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 ~ 5

见题目目录下的 2.in/2.ans ~ 5.in/5.ans。

数据范围

对 100% 数据，$1 \le T \le 100$，$1 \le l < r \le 10^{11}$。

提示

请注意 $l, r$ 的数据范围和 C/C++ 中 int 类型的取值范围。