在很多很多年之后,在很远很远的地方,将会发射第一次飞往火星的航班。为了庆祝成功,参与该项目的 $$$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$$$ 银币。
输入
在输入的第一行中,有一个整数 $$$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$$$) — 分别是公司的天体物理学家,分配的金币总数以及1枚金币对应的银币数量。
输出
在每个测试用例的单独行中,输出一个整数——由于舍入而可以节省的最大银币数量。
示例
输入 #1
5 3 3 100 2 1 14 91 2 13 36 16 6 73 8 22
输出 #1
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$$$ 银币,那么公司将必须支付额外的金币来支付奖金。