题目描述

你有一个被分成 $l$ 个区域的奖品转盘，这些区域编号从 $0$ 到 $l-1$。这些区域排列成一个圆环，所以在 $l-1$ 区域之后，编号又从 $0$ 区域重新开始。

初始时，指针指向第 $a$ 区域。每次转动转盘时，指针都会正好前进 $b$ 个区域。也就是说，转动一次后，指针会从第 $a$ 区域移动到第 $(a+b)\bmod l$ 区域；转动两次后到达第 $(a+2b)\bmod l$ 区域，依此类推$^*$。

你可以选择任意次数地转动转盘（包括零次）。当你停止时，指针最终停留的区域决定了你的奖品：你获得的奖金等于该区域的编号。

你能获得的最大奖金是多少？

$^*$ 这里，$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$。指针位置的序列为：$3, 0, 2, 4, 1, 3, 0, \ldots$。

在第二个测试数据中，指针会一直停留在第 $0$ 区域，不会改变。

在第四个测试数据中，$b=1$ 并且从第 $0$ 区域开始，指针会遍历所有区域，包括最后一个区域。

可视化链接

由 ChatGPT 5 翻译

样例

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

4
0
6
99