程序员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 在旅程结束时可能拥有的最大功率。
示例
输入复制
89 610 724 2123456 7776 499 610 499 4
输出复制
4 1 2 775 1 4 2 2
注意
第一个示例中 Gleb 运动的变体之一: