B. Разделение конфет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Деда Мороза есть $$$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$$$) — количество конфет и количество детей.

Выходные данные

Выведите ответ на каждый набор входных данных — максимальное количество конфет, которые Дед Мороз сможет дать детям таким образом, чтобы он был доволен.

Пример
Входные данные
5
5 2
19 4
12 7
6 2
100000 50010
Выходные данные
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$$$ конфет.