题目描述

小 Z 是一个活泼好动的孩子。有一天，她站在数轴上 $b$ 的位置，并准备开始沿着数轴的正半轴移动。小 Z 每移动一步，就会立刻沿着数轴的正半轴前进 $a$ 个单位。奇妙的是，$a,b$ 都是正整数，所以小 Z 任意时刻所处的位置也都是正整数。

小 Z 的幸运数字是一个正整数 $c$。小 Z 认为如果她移动到的位置恰好与 $c$ 互质，那么她认为这个位置是一个幸运位置。请你帮小 Z 计算她是否可以移动到幸运位置；如果可以，请计算出能移动到幸运位置的任意一个移动步数 $n$。

简洁题意：给定三个正整数 $a,b,c$，判断是否存在非负整数 $n$ 使 $(an+b, c)=1$，若存在求任意一个解，其中 $(\cdot, \cdot)$ 表示最大公因数。

输入格式

第一行为一个正整数 $T$，表示数据组数。接下来依次输入每组数据。

对于每组数据，输入为一行三个正整数 $a,b,c$，含义见题目描述。

对于所有的输入数据，都有 $1\le T \le {{ 10 }}, 1\le a,b,c < 10^{ {{ 2000 }} }$，所有输入数据均按照十进制给出。

输出格式

对于每组数据输出一行一个整数。如果找不到合法的移动步数 $n$ 输出 -1，否则输出一个非负整数表示一个合法的移动步数 $n$。

所有输出应按照十进制输出，每行输出的长度不得超过 ${{ 2000 }}$，测试数据将保证存在输出长度限制内的解。另外，请不要输出多余的空格及任何多余字符，并保证文末有换行符，否则可能将影 响评测程序对结果的判定。

样例数据

样例 1 输入

3
1 2 3
1 3 6
2 2 2

样例 1 输出

0
2
-1

样例 1 解释

对于第一组数据，$a=1,b=2,c=3$，此时 $b,c$ 已经互质，$n=0$ 是一个解； 对于第二组数据，$a=1,b=3,c=6$，取 $n=2$ 时有 $an+b=5$，与 $6$ 互质，因此是一个解； 对于第三组数据，$a=2,b=2,c=2$，于是 $an+b=2n+2$，对于任意 $n$ 都有 $(an+b,c)=2$，因此不存在这样的 $n$，故输出 -1。

样例数据

样例 2 输入

10
852473158087426181 40698107377421 34573878586
581501852629475409 3507820691986234 325392124094986
983001573592419694 12758046154806915 391181873366625
523432507089908187 22235351323484 99720444415644
547133061299817509 6492909838101120 234547940354112
315440975649541747 11555829815904864 467063676334080
439602165995515631 4284196383788100 23950691236800
8041598789940150 37468471223945472 3903034663348992
6871678354485379 19849006524667320 441009815372280
332133101579862271 12172161650895405 171736644454695

样例 2 输出

62
8653
209
9153
11
515
391
-1
109
23

样例 3

见下发文件中的 3.in 与 3.ans。