# Discrete Logarithm

AC一覧

## Problem Statement問題文

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.

この問題は $T$ ケース与えられる。

$X, Y, M$ が与えられる。$X^K \equiv Y (\bmod M)$ なる非負整数 $K$ のうち、最小を答えよ(存在しない場合は-1)。

なお、$0^0 = 1$ とします。

## Constraints制約

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

## Input入力

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


## Sampleサンプル

### # 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


Timelimit: 10 secs

Before submitting, please confirm terms and conditions