← 返回题目列表

Codeforces · 2091/G

G. 格莱布和划船

中文机器翻译题面 查看原题

程序员Gleb经常到访IT校园“NEIMARK”参加编程培训课程。

Gleb 不仅是一名程序员,而且还是一位著名的赛艇运动员,因此他从家到校园的部分旅程是沿着河划皮划艇。假设 Gleb 从点 $$$0$$$ 开始,必须到达点 $$$s$$$(即沿直线行进 $$$s$$$ 米)。为了使挑战变得更加艰巨,Gleb 决定不超出 $$$[0, s]$$$ 部分。皮划艇的尺寸可以忽略不计。

Gleb是一位强大的程序员!最初,他的力量是$$$k$$$。格莱布的力量直接影响他的皮划艇的运动。如果他当前的功率为 $$$x$$$,则划桨一次,皮划艇将沿当前方向移动 $$$x$$$ 米。格列布可以转身并继续向相反方向移动,但这样的操作相当具有挑战性,而且每次转身后,他的力量都会减少$$$1$$$。力量永远不会变成$$$0$$$——如果他当前的力量是$$$1$$$,那么即使在转变之后它仍然是$$$1$$$。此外,格列布不能连续转两圈——每转一圈后,他必须至少移动一次才能进行另一圈。同样,格列布不能在出发后立即转弯——他必须先划桨。

Gleb 希望从点 $$$0$$$ 到达点 $$$s$$$,而不离开线段 $$$[0, s]$$$,同时保留尽可能多的电量。帮助他 - 给定值 $$$s$$$ 和他的初始功率 $$$k$$$,确定他在到达 $$$s$$$ 点时可以拥有的最大可能功率。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 100$$$)。测试用例的描述如下。

每个测试用例的一行包含两个整数 $$$s$$$ 和 $$$k$$$ ($$$1 \leq s \leq 10^9$$$, $$$1 \leq k \leq 1000$$$, $$$k \leq s$$$)。

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

输出

对于每个测试用例,输出 Gleb 在旅程结束时可能拥有的最大功率。

示例

输入
复制

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

注意

第一个示例中 Gleb 运动的变体之一: