← 返回题目列表

Codeforces · 1283/B

B. 糖果事业部

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

圣诞老人有 $$$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$$$ 糖果。