#P2241. 负数取模

负数取模

问题描述

在数学中,正整数 mm 的模运算通常希望得到一个位于 [0,m−1][0,m-1] 内的结果。C++ 中负数参与 % 运算时,结果可能为负数。

给你 TT 组整数 a,ma,m,其中 m>0m>0。

你需要输出 aa 模 bb 的结果 rr。

输入格式

第一行一个整数 TT。接下来 TT 行,每行两个整数 a,ma,m。

输出格式

对每组数据输出一行一个整数,表示标准余数 rr。

样例输入

7
-7 5
-10 5
7 5
0 13
-1 1
-1 1000000000000000000
-1000000000000000000 999999999999999999

样例输出

3
0
2
0
0
999999999999999999
999999999999999998

说明

负数本身是 mm 的倍数时答案仍为 00。请使用64位有符号整数保存输入和答案。

评测数据规模

所有数据满足:1≤T≤2000001\le T\le 200000,−1018≤a≤1018-10^{18}\le a\le 10^{18},1≤m≤10181\le m\le 10^{18}。