小 A 和小 B 一起在玩一个游戏。

游戏一共有 n  个盒子排成一排，其中第 i 个盒子里面恰好装有 i 个小球（ i 从 1 开始）。游戏开始前，小 A 需要选择一个 1~M 内的整数K 。接下来，游戏进行第 j  轮时，小 B 会先拿走第 j 个盒子内的所有小球，然后小 A 会拿走第( (j\times K-1)mod n)+1 个盒子内的所有小球（有可能他们每个人选择的盒子内的小球都已经被拿走了，这个时候他们什么也不做）。

小 A 想知道：他要如何选择这个 K ，使得自己拿走的小球数量最多？如果有多个 K 符合要求，小 A 想知道最小的那一个K 是多少。

第一行输入一个正整数T ，表示数据组数。

对于每一组数据，输入两个正整数n,M ，分别表示盒子数量以及小 A 能选择的 K 的最大值。

对于每一组数据，请输出能使得小 A 拿的球最多的最小的K 。

在第一个样例中，小 A 只能选择 k=1，游戏过程如下：

• 小 B 选择第 1 个盒子并得到 1 个球，然后小 A 选择第 1 个盒子，得到 0 个球。

• 小 B 选择第 2 个盒子并得到 2 个球，然后小 A 选择第 2 个盒子，得到 0 个球。

• 小 B 选择第 3 个盒子并得到 3 个球，然后小 A 选择第 3 个盒子，得到 0 个球。

小 A 总共得到 0+0+0=0个球。

第二个样例中，小 A 选择 ，游戏过程如下：

• 小 B 选择第 1 个盒子并得到 1 个球，然后小 A 选择第 3 个盒子得到 3 个球。

• 小 B 选择第 2 个盒子并得到 2 个球，然后小 A 选择第 1 个盒子得到 0个球。

• 小 B 选择第 3 个盒子并得到 0 个球，然后小 A 选择第 4 个盒子得到 4个球。

• 小 B 选择第 4 个盒子并得到 0 个球，然后小 A 选择第 2 个盒子得到 0 个球。

• 小 B 选择第 5 个盒子并得到 5 个球，然后小 A 选择第 5 个盒子得到 0个球。

小 A 一共得到 3+4=7个球。可以求出  个球是小 A 能获得的最多的球，此时 k=3或 k=4都可以，而我们需要输出最小的，即 k=3。

数据说明：

对于 30% 的数据，1\leq n,M,T \leq 100;

对于 60% 的数据，1\leq n,M,T \leq 2000;

对于 100% 的数据，1\leq n \leq 10^9,1\leq M,T \leq 2000;