310454: CF1836B. Astrophysicists

B. Astrophysiciststime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Note that due to rounding, the total sum of actually paid money is not, in general, equal to $k \cdot g$ silver coins. The operation $a \bmod b$ denotes the remainder of the division of $a$ by $b$. Sum of values before rounding has to be equal to $k \cdot g$ silver coins, but some workers can be assigned $0$ 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

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

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.

ExampleInput

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

Output

100
0
26
72
176

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.

**题目大意：**

在很久很久以后的未来，将会发射第一艘前往火星的航班。为了庆祝这一成功，参与项目的n名天体物理学家将会获得总价值为k金币的奖金。你需要将这些钱以银币的形式分配给天体物理学家，每个金币值g银币，因此你需要将所有k*g银币分配给n人。

不幸的是，公司目前面临一些财务困难。因此，他们决定不是支付奖金上写的银币数量，而是将这个数量四舍五入到最接近的金币数。

四舍五入的规则如下：如果一名天体物理学家的奖金为x银币，我们设r = x mod g，则：
- 如果r ≥ ⌈g/2⌉，该天体物理学家收到x + (g - r)银币；
- 否则，该天体物理学家收到x - r银币。

请注意，由于四舍五入，实际支付的总金额通常不等于k*g银币。操作a mod b表示a除以b的余数。四舍五入前值的总和必须等于k*g银币，但可以将0银币分配给某些工人。

你的目标是分配奖金，使公司因四舍五入而节省尽可能多的银币。请注意，总有一种分配方式使得公司花费不超过k*g银币。

**输入数据格式：**

输入的第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。

接下来的t行，每行描述一个测试用例，并包含三个整数n、k、g（1 ≤ n ≤ 10^9，0 ≤ k ≤ 10^9，2 ≤ g ≤ 10^9）—— 分别是公司中的天体物理学家数量、要分配的总金币数和一枚金币对应的银币数。

**输出数据格式：**

对于每个测试用例，输出一行，包含一个整数——因四舍五入可能节省的最大银币数。

**示例：**

输入：
```
5
3 3 100
2 1 14
91 2 13
36 16 6
73 8 22
```

输出：
```
100
0
26
72
176
```**题目大意：** 在很久很久以后的未来，将会发射第一艘前往火星的航班。为了庆祝这一成功，参与项目的n名天体物理学家将会获得总价值为k金币的奖金。你需要将这些钱以银币的形式分配给天体物理学家，每个金币值g银币，因此你需要将所有k*g银币分配给n人。 不幸的是，公司目前面临一些财务困难。因此，他们决定不是支付奖金上写的银币数量，而是将这个数量四舍五入到最接近的金币数。 四舍五入的规则如下：如果一名天体物理学家的奖金为x银币，我们设r = x mod g，则： - 如果r ≥ ⌈g/2⌉，该天体物理学家收到x + (g - r)银币； - 否则，该天体物理学家收到x - r银币。 请注意，由于四舍五入，实际支付的总金额通常不等于k*g银币。操作a mod b表示a除以b的余数。四舍五入前值的总和必须等于k*g银币，但可以将0银币分配给某些工人。 你的目标是分配奖金，使公司因四舍五入而节省尽可能多的银币。请注意，总有一种分配方式使得公司花费不超过k*g银币。 **输入数据格式：** 输入的第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 接下来的t行，每行描述一个测试用例，并包含三个整数n、k、g（1 ≤ n ≤ 10^9，0 ≤ k ≤ 10^9，2 ≤ g ≤ 10^9）—— 分别是公司中的天体物理学家数量、要分配的总金币数和一枚金币对应的银币数。 **输出数据格式：** 对于每个测试用例，输出一行，包含一个整数——因四舍五入可能节省的最大银币数。 **示例：** 输入： ``` 5 3 3 100 2 1 14 91 2 13 36 16 6 73 8 22 ``` 输出： ``` 100 0 26 72 176 ```