Description

You are asked to design a calculator to complete the following three tasks:

1. Given $y, z, p$, compute the value of $y^z \bmod p$.
2. Given $y, z, p$, compute the smallest non-negative integer $x$ such that $xy \equiv z \pmod p$.
3. Given $y, z, p$, compute the smallest non-negative integer $x$ such that $y^x \equiv z \pmod p$.

Do your best to win the prize!

Input Format

The input contains multiple test cases.

The first line contains two positive integers $T, K$, denoting the number of test cases and the query type, respectively (for all testdata within a single test point, the query type is the same).

Each of the following $T$ lines contains three positive integers $y, z, p$, describing one query.

Output Format

The output contains $T$ lines.

For each query, output one line with the answer.

For query types $2$ and $3$, if no solution exists, output Orz, I cannot find x!.

3 1
2 1 3
2 2 3
2 3 3

2
1
2

3 2
2 1 3
2 2 3
2 3 3

2
1
0

4 3
2 1 3
2 2 3
2 3 3
2 4 3

0
1
Orz, I cannot find x!
0

Hint

Test points are divided into three categories. The proportion of each category among all test points is as follows:

All testdata satisfy: $1 \leq y, z, p \leq 10^9$, $p$ is prime, and $1 \leq T \leq 10$.

Translated by ChatGPT 5