Astrophysicists
Contest: Codeforces Round 880 (Div. 2)
Difficulty rating: 1100
Tags: greedy, math

In many, many years, far, far away, there will be a launch of the first flight to Mars. To celebrate the success, $$$n$$$ astrophysicists working on the project will be given bonuses of a total value of $$$k$$$ gold coins.

You have to distribute the money among the astrophysicists, and to make it easier, you have to assign bonuses in silver coins. Each gold coin is worth $$$g$$$ silver coins, so you have to distribute all $$$k \cdot g$$$ silver coins among $$$n$$$ people.

Unfortunately, the company has some financial troubles right now. Therefore, instead of paying the number of silver coins written on the bonus, they decided to round this amount to the nearest integer number of gold coins.

The rounding procedure is as follows. If an astrophysicist has bonus equal to $$$x$$$ silver coins, and we denote $$$r = x \bmod g$$$, then:

- If $$$r \geq \lceil \frac{g}{2} \rceil$$$, the astrophysicist receives $$$x + (g - r)$$$ silver coins;
- Otherwise, an astrophysicists receives $$$x - r$$$ silver coins.

You aim to distribute the bonuses so that the company saves as many silver coins due to rounding as possible. Please note that there is always a distribution in which the company spends no more than $$$k \cdot g$$$ silver coins.

Input format:
In the first line of input, there is one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) denoting the number of test cases.

Each of the following $$$t$$$ lines describes one test case and contains three integers $$$n$$$, $$$k$$$, $$$g$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le k \le 10^9$$$, $$$2 \le g \le 10^9$$$) — respectively the number of astrophysicists in the company, total number of gold coins to assign and the number of silver coins that one gold coin corresponds to.

Output format:
In a separate line for each test case, output a single integer — the maximum number of silver coins that could be saved due to rounding.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one of the optimal assignments could be the following:

- First person: $$$x = 30$$$ silver coins: company pays $$$0$$$, saves $$$30$$$ silver coins,
- Second person: $$$x = 140$$$ silver coins: company pays $$$100$$$, saves $$$40$$$ silver coins,
- Third person: $$$x = 130$$$ silver coins: company pays $$$100$$$, saves $$$30$$$ silver coins.

In the second test case, we could have the following assignment:

- First person: $$$x = 8$$$ silver coins: company pays $$$14$$$, spends extra $$$6$$$ silver coins,
- Second person: $$$x = 6$$$ silver coins: company pays $$$0$$$, saves $$$6$$$ silver coins.

If the bonuses are assigned to $$$7$$$ silver coins for both astrophysicists, then the company would have to pay an additional gold coin to cover the bonuses.

Example input:
5
3 3 100
2 1 14
91 2 13
36 16 6
73 8 22

Example output:
100
0
26
72
176

Editorial:
Note that in the perfect world, we'd give each astrophysicist precisely $$$\lfloor \frac{G - 1}{2} \rfloor$$$, and we'd spare $$$N \cdot \lfloor \frac{G - 1}{2} \rfloor$$$ silver coins. Unfortunately, two things may happen:
• First, we may run out of money. This is an easy case; it is enough to output $$$K \cdot G$$$ if it is less than $$$\lfloor \frac{G - 1}{2} \rfloor$$$.
• Second, we may have some money left. It turns out that an acceptable solution is to give everything to one astrophysicist. The intuition behind it is simple — we are only interested in bonus sizes modulo $$$G$$$, and by decreasing the bonus of one astrophysicist, we can get at most $$$1$$$ from another one, and by increasing it, we lose $$$\lfloor \frac{G - 1}{2} \rfloor$$$. In both cases, it is not worth changing the value.Thus, we got a formula to calculate in $$$\mathcal{O}(1)$$$.