解题思路

设数列为 $a_i=a_0+i\cdot d$，我们关心的是所有 $a_i \bmod m$ 的取值。

先把问题转化到模 $m$ 的意义下：

• 起点变成 $a_0 \bmod m$
• 公差变成 $d \bmod m$

题目内容

给定一个无穷项等差数列 $a_i=a_0+i⋅d（i≥0）$，以及一个正整数 $m$。定义余数为 $a_i$ $mod$ $m$（取值范围为 $[0,m)$）。请你计算在所有 $i≥0$ 中，$a_i$ $mod$ $m$ 的最大可能值，并输出该最大值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T（1≤T≤10^5）$ 表示数据组数。 每组测试数据描述如下：一行输入三个整数 $a_0, d, m（0≤a_0,d≤10^{18}, 1≤m≤10^{18}）$。

输出描述

对于每组测试数据，输出一行一个整数，表示能得到的最大值。

样例1

输入

3
5 4 7
3 10 6
100 100 100

输出

6
5
0