题目内容

小 A 有一个特殊的计数器，它的显示屏只能显示 $0$ 到 $M-1$ 之间的整数。初始时，屏幕上显示的数字为 $s$。

每按下一次按钮，计数器会将当前显示的数字加上一个固定的增量 $p$。如果结果大于或等于 $M$，屏幕会自动将结果对 $M$ 取模，即减去若干个 $M$，使显示值重新落在 $[0, M-1]$ 范围内。

小 A 可以按任意多次按钮（包括零次）。设第 $i$ 次操作后显示的值为 $v_i$（规定 $v_0 = s$）。请计算在无限多次操作中，$v_i$ 能达到的最大值是多少。

问题约束：

• 初始值 $s$ 和增量 $p$ 均为不超过 $10^{18}$ 的非负整数。
• 模数 $M$ 为不超过 $10^{18}$ 的正整数。
• 测试数据组数不超过 $10^5$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来 $T$ 行，每行包含三个整数 $s$, $p$, $M$，分别表示初始值、增量和模数。

输出描述

对于每组测试数据，输出一行一个整数，表示在任意多次操作后屏幕能显示的最大值。

样例1

输入

3
10 6 15
1 2 8
5 7 1

输出

13
7
0

说明

包含三组测试数据：

第一组：初始值 $s=10$，增量 $p=6$，模数 $M=15$。 计算 $g = \gcd(6, 15) = 3$，然后 $r = 10 \bmod 3 = 1$。 最大值为 $M - g + r = 15 - 3 + 1 = 13$。 实际显示序列为 $10, 1, 7, 13, 4, 10, \dots$，最大值确实是 13。

第二组：$s=1$，$p=2$，$M=8$。 $g = \gcd(2, 8) = 2$，$r = 1 \bmod 2 = 1$。 最大值为 $8 - 2 + 1 = 7$。 显示序列为 $1, 3, 5, 7, 1, \dots$，最大值 7。

第三组：$s=5$，$p=7$，$M=1$（边界情况）。 因为 $M=1$，$g = \gcd(7, 1) = 1$，$r = 5 \bmod 1 = 0$。 最大值为 $1 - 1 + 0 = 0$。 屏幕只能显示 $0$，无论按多少次按钮，最大值始终为 0。