您的奖品轮盘分为 $$$l$$$ 部分,编号从 $$$0$$$ 到 $$$l-1$$$。这些部分排列成一个圆圈,因此在 $$$l-1$$$ 部分之后,编号再次从 $$$0$$$ 部分继续。
最初,奖品指针位于 $$$a$$$ 部分。每次旋转滚轮时,指针都会向前移动 $$$b$$$ 部分。也就是说,一次旋转后,指针从 $$$a$$$ 部分移动到 $$$(a+b)\bmod l$$$ 部分,两次旋转后移动到 $$$(a+2b)\bmod l$$$,依此类推 $$$^{\text{*}}$$$。
您可以旋转轮盘任意次数(包括零次)。停止后,指针最终落在的部分将决定您的奖品:您将收到等于该部分编号的金额。
您可以获得的最高奖金是多少?
$$$^{\text{*}}$$$这里,$$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 所得的余数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$l、a$$$ 和 $$$b$$$($$$1 \le l、b \le 5000$$$、$$$0 \le a \le l-1$$$)。
输出
对于每个测试用例,输出可以获得的最高奖金。
示例
输入复制
45 3 22 0 68 2 4100 0 1
输出复制
40699
注意
在第一个测试用例中,通过旋转轮子 3 次然后领取奖励,您可以获得的最大值为 $$$4$$$。指针位置的顺序为:$$$3, 0, 2, 4, 1, 3, 0, \ldots$$$
在第二个测试用例中,指针将无限期地保留在 $$$0$$$ 部分。
在第四个测试用例中,$$$b = 1$$$ 并从 $$$0$$$ 部分开始,指针将迭代所有部分,包括最后一个部分。
链接到可视化工具