Exponential Equation 1

Problem Description

Answer $T$ queries. Each query gives three numbers $a, b, m$; output the smallest non-negative integer $x$ satisfying $a^x \equiv b \pmod m$.

Input Format

The first line contains an integer $T$. The next $T$ lines each contain three integers $a, b, m$.

Output Format

One integer: the smallest non-negative solution; if no solution exists, output -1.

Sample Input

4
3 7 10
688720331 114514 998244353
5 114514 998244353
688720331 407057022 998244353

Sample Output

3
-1
271880075
123

Constraints

For all data, $T\leq 100$, $1\leq a, b < m \leq 10^9$ are guaranteed, and $a$ is coprime to $m$.