题目描述

$T$ 次询问，每次给两个正整数 $a,b$，请输出他们的次大公因数。

如果只有一个公因数（不存在次大公因数），输出 -1

输入格式

第一行一个数 $T$。

接下来 $T$，每行两个整数，即当前的询问。

输出格式

输出 $T$ 行，每行为一次询问的答案。

5
100 100
100 50
100 10
100 33
100 5

50
25
5
-1
1

数据规模与约定

对于 $100\%$ 的数据，$1 \le T \le 5000$，$1\le a,b\le 10^7$。

• 子任务 1（30 分）：$1\le a,b\le 100$。
• 子任务 2（30 分）：$1\le a,b\le 5000$。
• 子任务 3（40 分）：没有特殊限制。