圣诞老人有 $$$n$$$ 糖果,他想把它们送给 $$$k$$$ 孩子。他想把尽可能多的糖果分给所有 $$$k$$$ 孩子。圣诞老人无法将一颗糖果分成几部分,但他可以完全不使用某些糖果。
假设收到最少糖果的孩子有 $$$a$$$ 糖果,收到最多糖果的孩子有 $$$b$$$ 糖果。如果同时满足这两个条件,圣诞老人就会满意:
- $$$b - a \le 1$$$ (这意味着 $$$b = a$$$ 或 $$$b = a + 1$$$);
- 拥有$$$a+1$$$糖果(注意$$$a+1$$$不一定等于$$$b$$$)的孩子数量不超过$$$\lfloor\frac{k}{2}\rfloor$$$(小于或等于$$$\lfloor\frac{k}{2}\rfloor$$$)。
$$$\lfloor\frac{k}{2}\rfloor$$$ 是 $$$k$$$ 除以 $$$2$$$ 并向下舍入到最接近的整数。例如,如果 $$$k=5$$$ 则 $$$\lfloor\frac{k}{2}\rfloor=\lfloor\frac{5}{2}\rfloor=2$$$。
你的任务是找到圣诞老人可以给孩子们的最大糖果数量,这样他就会感到满意。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 测试用例的数量。
接下来的 $$$t$$$ 行描述测试用例。第 $$$i$$$ 测试用例包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 10^9$$$) — 糖果的数量和孩子的数量。
输出
对于每个测试用例,请在其上打印答案 - 圣诞老人可以给孩子们的最大糖果数量,以便他感到满意。
示例
输入 #1
5 5 2 19 4 12 7 6 2 100000 50010
输出 #1
5 18 10 6 75015
注意
在第一个测试用例中,圣诞老人可以给孩子们 $$$3$$$ 和 $$$2$$$ 糖果。有$$$a=2,b=3,a+1=3$$$。
在第二个测试用例中,圣诞老人可以给予 $$$5、5、4$$$ 和 $$$4$$$ 糖果。有$$$a=4,b=5,a+1=5$$$。答案不能再大了,因为这样的话,拥有 $$$5$$$ 糖果的孩子的数量将是 $$$3$$$。
在第三个测试用例中,圣诞老人可以通过以下方式分发糖果:$$$[1, 2, 2, 1, 1, 2, 1]$$$。有$$$a=1,b=2,a+1=2$$$。他无法以令人满意的方式分配剩余的两颗糖果。
在第四个测试用例中,圣诞老人可以通过以下方式分发糖果:$$$[3, 3]$$$。有$$$a=3,b=3,a+1=4$$$。圣诞老人分发了所有 $$$6$$$ 糖果。