Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Candies Division

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSanta has $$$n$$$ candies and he wants to gift them to $$$k$$$ kids. He wants to divide as many candies as possible between all $$$k$$$ kids. Santa can't divide one candy into parts but he is allowed to not use some candies at all.

Suppose the kid who recieves the minimum number of candies has $$$a$$$ candies and the kid who recieves the maximum number of candies has $$$b$$$ candies. Then Santa will be satisfied, if the both conditions are met at the same time:

- $$$b - a \le 1$$$ (it means $$$b = a$$$ or $$$b = a + 1$$$);
- the number of kids who has $$$a+1$$$ candies (note that $$$a+1$$$ not necessarily equals $$$b$$$) does not exceed $$$\lfloor\frac{k}{2}\rfloor$$$ (less than or equal to $$$\lfloor\frac{k}{2}\rfloor$$$).

$$$\lfloor\frac{k}{2}\rfloor$$$ is $$$k$$$ divided by $$$2$$$ and rounded down to the nearest integer. For example, if $$$k=5$$$ then $$$\lfloor\frac{k}{2}\rfloor=\lfloor\frac{5}{2}\rfloor=2$$$.

Your task is to find the maximum number of candies Santa can give to kids so that he will be satisfied.

You have to answer $$$t$$$ independent test cases.

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases.

The next $$$t$$$ lines describe test cases. The $$$i$$$-th test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$) — the number of candies and the number of kids.

Output

For each test case print the answer on it — the maximum number of candies Santa can give to kids so that he will be satisfied.

Example

Input

5 5 2 19 4 12 7 6 2 100000 50010

Output

5 18 10 6 75015

Note

In the first test case, Santa can give $$$3$$$ and $$$2$$$ candies to kids. There $$$a=2, b=3,a+1=3$$$.

In the second test case, Santa can give $$$5, 5, 4$$$ and $$$4$$$ candies. There $$$a=4,b=5,a+1=5$$$. The answer cannot be greater because then the number of kids with $$$5$$$ candies will be $$$3$$$.

In the third test case, Santa can distribute candies in the following way: $$$[1, 2, 2, 1, 1, 2, 1]$$$. There $$$a=1,b=2,a+1=2$$$. He cannot distribute two remaining candies in a way to be satisfied.

In the fourth test case, Santa can distribute candies in the following way: $$$[3, 3]$$$. There $$$a=3, b=3, a+1=4$$$. Santa distributed all $$$6$$$ candies.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2020 19:25:10 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|