CF1836B.Astrophysicists

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.

在很久、很久以后，遥远、遥远的地方，人类将首次发射飞往火星的航天器。为庆祝这一成功，参与该项目的 $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$ 枚银币，但允许某些员工被分配 $0$ 枚银币。

你的目标是分配奖金，使得公司因四舍五入而节省的银币数量尽可能多。请注意，总存在一种分配方式，使得公司实际支出的银币总数不超过 $k \cdot g$ 枚。

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.

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

接下来的 $t$ 行每行描述一个测试用例，包含三个整数 $n$、$k$、$g$（$1 \leq n \leq 10^9$，$0 \leq k \leq 10^9$，$2 \leq g \leq 10^9$），分别表示公司中天体物理学家的人数、需分配的金币总数，以及一枚金币所对应的银币数量。

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.

对于每个测试用例，在单独的一行中输出一个整数——因四舍五入而最多可节省的银币数量。

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.

在第一个测试用例中，一种最优的分配方案如下：

• 第一个人：$x = 30$ 枚银币：公司支付 $0$，节省 $30$ 枚银币；
• 第二个人：$x = 140$ 枚银币：公司支付 $100$，节省 $40$ 枚银币；
• 第三个人：$x = 130$ 枚银币：公司支付 $100$，节省 $30$ 枚银币。

在第二个测试用例中，可采用如下分配方案：

• 第一个人：$x = 8$ 枚银币：公司支付 $14$，额外支出 $6$ 枚银币；
• 第二个人：$x = 6$ 枚银币：公司支付 $0$，节省 $6$ 枚银币。

若两位天体物理学家均被分配 $7$ 枚银币的奖金，则公司需额外支付一枚金币以覆盖奖金。