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

Через много-много лет, далеко-далеко, состоится запуск первого полета на Марс. В честь этого успеха $$$n$$$ астрофизикам, работающим над проектом, будут выданы премии общей стоимостью $$$k$$$ золотых монет.

Вам нужно распределить деньги по астрофизикам, и чтобы это было проще сделать, вы номинируете бонусы в серебряных монетах. Каждая золотая монета равна $$$g$$$ серебряным, поэтому вам нужно распределить $$$k \cdot g$$$ серебряных монет по $$$n$$$ людям.

К сожалению, компания сейчас испытывает некоторые финансовые трудности. Поэтому вместо того, чтобы выплатить написанное на бонусе количество серебряных монет, они решили округлить эту сумму до ближайшего целого числа золотых монет.

Процедура округления выглядит следующим образом. Если премия астрофизика равна $$$x$$$ серебряных монет, и мы обозначаем $$$r = x \bmod g$$$, то:

  • Если $$$r \geq \lceil \frac{g}{2} \rceil$$$, то астрофизик должен получить $$$x + (g - r)$$$ серебряных монет;
  • Иначе астрофизик должен получить $$$x - r$$$ серебряных монет.
Обратите внимание, что из-за округления сумма фактически выплаченных денег в общем случае не равна $$$k \cdot g$$$ серебряным монетам. Операция $$$a \bmod b$$$ обозначает взятие остатка от деления $$$a$$$ на $$$b$$$.

Вы стремитесь распределить премии так, чтобы компания из-за округления сохранила как можно больше серебряных монет. Обратите внимание, что всегда существует распределение, при котором компания платит не больше $$$k \cdot g$$$ серебряных монет.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$, $$$g$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le k \le 10^9$$$, $$$2 \le g \le 10^9$$$) — количество астрофизиков в компании, общая сумма премий в золотых монетах и количество серебряных монет, которому соответствует одна золотая монета.

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

Для каждого набора входных данных в отдельной строке выведите одно целое число — максимальное количество серебряных монет, которое может остаться от начальной суммы после выплаты всех премий.

Пример
Входные данные
5
3 3 100
2 1 14
91 2 13
36 16 6
73 8 22
Выходные данные
100
0
26
72
176
Примечание

В первом наборе входных данных одно из оптимальных назначений может быть следующим:

  • Первый физик, $$$x = 30$$$ серебряных монет: компания выплачивает $$$0$$$, экономит $$$30$$$ серебряных монет.
  • Второй физик, $$$x = 140$$$ серебряных монет: компания выплачивает $$$100$$$, экономит $$$40$$$ серебряных монет.
  • Третий физик, $$$x = 130$$$ серебряных монет: компания выплачивает $$$100$$$, экономит $$$30$$$ серебряных монет.

Во втором наборе мы могли бы использовать следующее распределение:

  • Первый физик, $$$x = 8$$$ серебряных монет: после округления компания выплачивает $$$14$$$ монет, тратит дополнительно $$$6$$$ серебряных монет.
  • Второй физик, $$$x = 6$$$ серебряных монет: компания выплачивает $$$0$$$, экономит $$$6$$$ серебряных монет.

Если же будет назначена премия в размере $$$7$$$ серебряных монет для обоих астрофизиков, то компания должна будет заплатить дополнительную золотую монету.