一日之计在于晨
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

俗话说"一日之计在于晨"，pei_pei_现在正在为自己的未来而奋斗；
但是每当pei_pei_沐浴着夕阳与月光才开始学习时，他都对自己深恶痛绝；
他决定使用时间回溯魔法为自己争取到最多的时间来学习。
以上为题目背景；

pei_pei_有一个只有一根指针的神奇钟表，他可以通过拨动指针使得现实的时间发生改变；
① 该钟表的钟面刻度分为 m 格，将一天均分成 m 份。(每个刻度代表一天的一个时刻，数字 1\sim m 均匀顺序地分布在圆形钟表上，刻度 i 的下一个刻度是 i\bmod m + 1)。
② 初始时指针指向 t 刻度。
③ pei_pei_ 每次可以选择朝一个方向（顺时针或逆时针方向）移动 a 刻度。允许拨动任意多次（可能 0 次）指针，指针最后指向的刻度就是回溯到的时刻。

pei_pei_ 想要尽早开始今天的学习，他希望指针可以指向它能指向的刻度中刻度最小的位置，请帮 pei_pei_ 找到最少的拨动次数使得指针指向刻度最小的位置。


为了不误导您，向您指出：题目所要求的是指向它能指向的刻度中刻度最小的位置，如果指针指向 $m$ 时刻不等同其回到 $0$ 时刻，其依旧是 $m$ 时刻。

输入描述:

第一行一个整数 n (1 \leq n \leq 10^5)，代表测试用例的数量；

接下来 n 行，每行 3 个整数t,a,m (1 \leq {t}\leq{m} \leq 10^9,1\leq{a}\leq 10^9)，表示指针初始指向t刻度，每次可以移动a刻度，以及钟面刻度被分为m格。

输出描述:

对于每个测试用例，输出一个整数 ans，表示最少的波动次数使得指针指向刻度最小的位置。
示例1

输入

复制 
5
1 1 2
2 13 2
5 5 6
6 3 10
2 8 24

输出

复制 
0
1
2
5
0

说明

第一个样例中，指针初始指向刻度1，已经到达该钟表所能到达的最小的刻度，所以最少需要0次波动次数。
第二个样例中，指针初始指向刻度2，向顺时针波动1次，指针移动13格后指向刻度1，所以最少需要1次波动次数。
第三个样例中，指针初始指向刻度5，向逆时针波动2次，指针指向变化为 5 -> 6 -> 1，所以最少需要2次波动次数。
第四个样例中，指针初始指向刻度6，向顺时针波动5次，指针指向变化为 6 -> 9 -> 2 -> 5 -> 8 -> 1， 所以最少需要5次波动次数。
第四个样例中，指针初始指向刻度2，已经到达该钟表所能到达的最小的刻度，所以最少需要0次波动次数。

备注: