У Деда Мороза есть \(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\) независимых наборов входных данных.
Выходные данные
Выведите ответ на каждый набор входных данных — максимальное количество конфет, которые Дед Мороз сможет дать детям таким образом, чтобы он был доволен.
Примечание
В первом наборе входных данных Дед Мороз может дать \(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\) конфет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 2
19 4
12 7
6 2
100000 50010
|
5
18
10
6
75015
|