P7611 [THUPC 2021] 幸运位置

小 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$，测试数据将保证存在输出长度限制内的解。另外，请不要输出多余的空格及任何多余字符，并保证文末有换行符，否则可能将影响评测程序对结果的判定。

**【样例解释】** 对于第一组数据，$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`。 **【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。 题解等资源可在 [https://github.com/yylidiw/thupc_2/tree/master](https://github.com/yylidiw/thupc_2/tree/master) 查看。