G. 格列布与划船
每个测试点时间限制：3 秒
内存限制：256 兆字节

程序员格列布经常访问 IT 校园 "NEIMARK" 参加编程训练。

格列布不仅是一名程序员，还是一位著名的划船运动员，因此他从家到校园的部分路程是沿着河流划皮划艇完成的。假设格列布从点 $0$ 出发，必须到达点 $s$（即沿直线行驶 $s$ 米）。为了使挑战更加艰难，格列布决定不离开区间 $[0, s]$。皮划艇的尺寸可以忽略不计。

格列布是一名强大的程序员！他的初始力量为 $k$。格列布的力量直接影响皮划艇的移动。如果他的当前力量为 $x$，那么一次划桨可以使皮划艇沿当前方向移动 $x$ 米。格列布可以调转方向并继续向相反方向移动，但这样的操作非常费力，每次调头后他的力量会减少 $1$。力量永远不会变为 $0$ —— 如果他的当前力量是 $1$，那么即使调头后它仍然是 $1$。此外，格列布不能连续调头两次 —— 每次调头后，他必须至少移动一次才能再次调头。同样，格列布不能在出发后立即调头 —— 他必须先进行一次划桨。

格列布希望在不离开区间 $[0, s]$ 的情况下从点 $0$ 到达点 $s$，并尽可能多地保留力量。请帮助他 —— 给定 $s$ 和他的初始力量 $k$，确定他到达点 $s$ 时可能拥有的最大力量。

输入格式

每个测试文件包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。每个测试用例的描述如下：

每个测试用例只有一行，包含两个整数 $s$ 和 $k$（$1 \le s \le 10^9$，$1 \le k \le 1000$，$k \le s$）。

保证所有测试用例的 $k$ 之和不超过 $2000$。

输出格式

对于每个测试用例，输出格列布到达点 $s$ 时可能拥有的最大力量。

示例输入

8
9 6
10 7
24 2
123456 777
6 4
99 6
10 4
99 4

示例输出

4
1
2
775
1
4
2
2

提示

第一个示例中格列布移动的一种方式：
（图示）