题目描述

你正在研究一个圆环形的能量核心装置。该装置由 $l$ 个能量槽组成，按顺时针方向依次编号为 $0$ 到 $l-1$。由于是环形结构，编号 $l-1$ 的下一个能量槽是编号 $0$。

初始时刻，核心的“激活指针”指向编号为 $a$ 的能量槽。该装置处于不稳定状态，每过一个单位时间，指针会顺时针跳跃 $b$ 个位置。

具体来说：

• 初始位置为 $a$。
• 1 个单位时间后，指针移动到 $(a + b) \bmod l$。
• 2 个单位时间后，指针移动到 $(a + 2b) \bmod l$。
• 以此类推...

作为观察者，你可以在任意时刻（包括初始时刻）记录下指针当前所指能量槽的编号作为“能量值”。由于指针会不断跳跃并可能形成循环，你希望知道在这个过程中，你所能记录到的最大能量值是多少。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 500$)，表示测试数据的组数。

接下来 $t$ 行，每行包含三个整数 $l, a, b$ ($1 \le l, b \le 5000$, $0 \le a \le l-1$)，分别表示能量槽的总数、初始位置和每次跳跃的步长。

输出格式

对于每组测试数据，输出一行，表示指针能经过的能量槽编号的最大值。

输入输出样例 #1

输入 #1

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

输出 #1

4
0
6
99