问题 3600 --扩展欧几里得算法2

3600: 扩展欧几里得算法2

时间限制: 1 Sec  内存限制: 256 MB
提交: 8  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

给定n对正整数ai,bi，对于每对数，求出一组 xi,yi，使其满足ai×xi+bi×yi=d。如果有解，要求xi是最小的非负整数。对于该题只输出xi的值即可。如果无解输出-1

输入

第一行包含整数 n。

接下来n行，每行包含三个整数 ai,bi,di。

输出

输出共n行，对于每组 ai,bi，输出每个满足条件的最小的非负整数xi的值。

样例输入

2
4 6 7
8 18 2

样例输出

-1
16

提示

1≤n≤10^5



1≤ai,bi,di≤2×10^9

来源

数论 扩展欧几里得算法 

[提交][状态]