离散对数 (Discrete Logarithm)

时间限制：10 秒

题目描述

每个测试包含 $T$ 组数据。

给定 $X, Y, M$。输出满足 $X^K \equiv Y \pmod M$ 的最小非负整数 $K$；若不存在这样的 $K$，则输出 $-1$。

注意，在本题中约定 $0^0 = 1$。

约束条件

• $1 \le T \le 100$
• $0 \le X, Y < M$
• $1 \le M \le 10^9$

输入

T
X_0 Y_0 M_0
X_1 Y_1 M_1
⋮
X_{T-1} Y_{T-1} M_{T-1}

输出

对于每一行，输出答案。

7
2 1 5
4 7 10
8 6 10
5 2 11
5 9 11
0 0 1
0 2 4

0
-1
4
-1
4
0
-1