题目描述

翁老师买了 $q$ 块长为 $p$ 个单位，宽为 $1$ 个单位的巧克力条。

这一天，翁老师将它们拼成了一整块大小为 $p\times q$ 的长方形巧克力，然后就出门了。聪聪老师醒来后发现了这块巨型巧克力，他决定从上面切一部分吃掉。

但这都在翁老师的预料之中----聪聪老师发现翁老师留下了一张字条：

• 你只可以从 其中一条 巧克力上切下长为正整数的一部分吃掉，但不能吃掉一整条。
• 我希望你吃掉的巧克力大小与剩下的巧克力大小的最大公因数尽可能大。
• 满足上一条的前提下，你应该给我留下尽可能多的巧克力。

聪聪老师非常火大，但他确实不擅长数学。请你帮助聪聪老师计算他能吃掉多少单位的巧克力。

什么是最大公因数？

• 两个整数 $a,b$ 的公因数指的是 $a,b$ 都有的公共因子。在公共因子中，最大的那个称为最大公因数。例如 $12$ 和 $8$ 的公因子有 $1,2,4$。而 $3$ 不是公因子，因为 $3$ 是 $12$ 的因子，但不是 $8$ 的因子。最大的公因子显然是 $4$。因此 $12$ 和 $8$ 的最大公因子是 $4$。数学上常用 $\gcd$ 代表最大公因数。记作 $\gcd(12,8)=4$。

输入格式

输入有多组数据。

第一行输入一个整数 $t$ 代表有 $t$ 组数据。

对于每组数据，有一行两个空格分隔的正整数 $p,q$

输出格式

对于每组数据，输出一行一个正整数代表答案。

3
2 4
3 5
6 7

1
1
3

样例 1 解释

对于第一组数据：$p=2$，吃巧克力的量必须是正整数，而且不能吃掉一整条，所以聪聪老师只能吃掉 $1$ 单位巧克力。

对于第二组数据：$p=3$，聪聪老师可以选择吃掉 $1$ 或者 $2$ 单位的巧克力。

• 如果吃掉 $1$ 单位，则剩余 $3\times 5-1=14$ 单位，$1$ 和 $14$ 的最大公因数为 $1$。
• 如果吃掉 $2$ 单位，则剩余 $3\times 5-2=13$ 单位， $2$ 和 $13$ 的最大公因数为 $1$。

两种方案的最大公因数相同时，要使剩余的巧克力尽量多，所以聪聪老师选择吃掉 $1$ 单位巧克力。

对于第三组数据：$p=6$，聪聪老师可以选择吃掉 $1,2,3,4$ 或者 $5$ 单位的巧克力。

• 如果吃掉 $1$ 单位，则剩余 $41$ 单位，$1$ 和 $41$ 的最大公因数为 $1$。
• 如果吃掉 $2$ 单位，则剩余 $40$ 单位，$2$ 和 $40$ 的最大公因数为 $2$。
• 如果吃掉 $3$ 单位，则剩余 $39$ 单位，$3$ 和 $39$ 的最大公因数为 $3$。
• 如果吃掉 $4$ 单位，则剩余 $38$ 单位，$4$ 和 $38$ 的最大公因数为 $2$。
• 如果吃掉 $5$ 单位，则剩余 $37$ 单位，$5$ 和 $37$ 的最大公因数为 $1$。

吃掉 $3$ 单位的方案中，吃掉的量与剩余的量的最大公因数最大，于是聪聪老师选择吃掉 $3$ 单位巧克力。

样例 2

点我下载大样例

数据范围

对于所有数据保证 $1\leq t\leq 50$，$2\leq p\leq 10^6$，$1\leq q\leq 10^{12}$。