小明报名参加了趣味运动会，游戏规则如下：

在一个环形跑道上，等距离放置着 $N$ 个小球，小球按照顺时针方向从起点依次标号，从 $1$ 到 $N$。谁能在最短的时间内取走放在跑道上的尽可能多的小球，谁就赢啦。但是举办方设定了一个特殊的规则，每个选手只能按照顺时针方向，跳过 $M-1$ 个号码取走下一个小球，比如

当 $N=5,M=3$ 时，小明能够取走所有的小球，取走的顺序依次为 $1\to 4\to 2\to 5\to 3$。
当 $N=6,M=2$ 时，小明只能取走 $3$ 个小球 $1\to 3\to 5$。

小明想知道在一场比赛中他最多能取走多少小球，当然，小明是知道怎么做的，但是他忙着补微积分作业，所以这个简单的问题就交(shuai guo)给你了。

第一行有一个整数 $T\ (1\le T\le 20)$，代表接下来有 $T$ 组样例

对于每一组样例，输入两个整数 $N,M\ (3\le N\le 10^8, 1\le M\le 10^8, N\ge M)$

在一场比赛中他最多能取走小球的个数