Little Z is a lively and active child. One day, she stands at position $b$ on the number line and prepares to move along the positive axis. Each time Little Z moves, she immediately advances $a$ units along the positive direction of the number line. Interestingly, $a$ and $b$ are both positive integers, so Little Z's position at any moment is also a positive integer.

Little Z's lucky number is a positive integer $c$. Little Z considers a position to be a "lucky position" if the position she reaches is coprime to $c$. Please help Little Z calculate whether she can reach a lucky position; if she can, calculate any number of steps $n$ that leads to a lucky position.

Simplified problem statement: Given three positive integers $a, b, c$, determine whether there exists a non-negative integer $n$ such that $(an+b, c)=1$. If it exists, find any such solution, where $(\cdot, \cdot)$ denotes the greatest common divisor.

Input

The first line contains a positive integer $T$, representing the number of test cases. The following lines contain the input for each test case.

For each test case, the input consists of a single line containing three positive integers $a, b, c$, with meanings as described in the problem statement.

For all input data, $1 \le T \le 10$ and $1 \le a, b, c < 10^{2000}$. All input data are given in decimal.

Output

For each test case, output a single integer on a new line. If no valid number of steps $n$ can be found, output -1; otherwise, output a non-negative integer representing a valid number of steps $n$.

All outputs should be in decimal. The length of each output line must not exceed $2000$. The test data guarantees that a solution within the output length limit exists. Additionally, please do not output extra spaces or any redundant characters, and ensure there is a newline character at the end of the file, otherwise it may affect the evaluation program's judgment of the result.

Examples

Input 1

3
1 2 3
1 3 6
2 2 2

Output 1

0
2
-1

Note 1

For the first test case, $a=1, b=2, c=3$. Since $b$ and $c$ are already coprime, $n=0$ is a solution. For the second test case, $a=1, b=3, c=6$. Taking $n=2$ gives $an+b=5$, which is coprime to $6$, so it is a solution. For the third test case, $a=2, b=2, c=2$. Then $an+b=2n+2$. For any $n$, $(an+b, c)=2$, so no such $n$ exists, and thus we output -1.

Input 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

Output 2

62
8653
209
9153
11
515
391
-1
109
23

Examples 3

See 3.in and 3.ans in the provided files.