题目描述

在遥远的未来，将会有第一次飞往火星的航班发射。为了庆祝这一成功，参与该项目的 $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$。

输入格式

输入的第一行包含一个整数 $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$），分别表示公司中的天体物理学家人数、要分配的金币总数以及一枚金币对应的银币数。

输出格式

对于每个测试用例，输出一行一个整数，表示通过四舍五入最多可以节省的银币数。

说明/提示

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

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

在第二个测试用例中，可以有如下分配：

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

如果两位天体物理学家都分配 $7$ 枚银币，则公司需要额外支付一枚金币来覆盖奖金。

由 ChatGPT 4.1 翻译

样例

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

100
0
26
72
176