← 返回题目列表

Codeforces · 2180/A

A. 嘉年华轮

中文机器翻译题面 查看原题

您的奖品轮盘分为 $$$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$$$)。

输出

对于每个测试用例,输出可以获得的最高奖金。

示例

输入
复制

4
5 3 2
2 0 6
8 2 4
100 0 1

输出
复制

4
0
6
99

注意

在第一个测试用例中,通过旋转轮子 3 次然后领取奖励,您可以获得的最大值为 $$$4$$$。指针位置的顺序为:$$$3, 0, 2, 4, 1, 3, 0, \ldots$$$

在第二个测试用例中,指针将无限期地保留在 $$$0$$$ 部分。

在第四个测试用例中,$$$b = 1$$$ 并从 $$$0$$$ 部分开始,指针将迭代所有部分,包括最后一个部分。

链接到可视化工具