8997: [yosupo] Number Theory - Discrete Logarithm
[Creator : ]
Description
Each test case consist of $T$ cases.
Given $X, Y, M$. Print the minimum non-negative integer $K$ s.t. $X^K \equiv Y (\bmod M)$, or $-1$ if there is no such $K$.
We note that $0^0 = 1$ in this problem.
Given $X, Y, M$. Print the minimum non-negative integer $K$ s.t. $X^K \equiv Y (\bmod M)$, or $-1$ if there is no such $K$.
We note that $0^0 = 1$ in this problem.
Input
$T$
$X_0$ $Y_0$ $M_0$
$X_1$ $Y_1$ $M_1$
:
$X_{T - 1}$ $Y_{T - 1}$ $M_{T - 1}$
$X_0$ $Y_0$ $M_0$
$X_1$ $Y_1$ $M_1$
:
$X_{T - 1}$ $Y_{T - 1}$ $M_{T - 1}$
Output
For each line, print answer.
Constraints
$1 \leq T \leq 100$
$0 \leq X, Y < M$
$1 \leq M \leq 10^9$
$0 \leq X, Y < M$
$1 \leq M \leq 10^9$
Sample 1 Input
7
2 1 5
4 7 10
8 6 10
5 2 11
5 9 11
0 0 1
0 2 4
Sample 1 Output
0
-1
4
-1
4
0
-1