Description

Original source: SDOI 2011

You are asked to design a calculator to perform 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 $x\times y\equiv z\ (\bmod p\ )$;
3. Given $y,z,p$, compute the smallest non-negative integer $x$ such that $y^x\equiv z\ (\bmod p\ )$.

Input Format

The input contains multiple test cases.

The first line contains two positive integers $T,K$ representing the number of test cases and the query type (for all data within a test case, the query type is the same);
Each of the next $T$ lines contains three positive integers $y,z,p$, describing a query.

Output Format

For each query, output one line with the answer.

For query types $2$ and $3$, if there is no solution, output Orz, I cannot find x!. Note there is a space between the comma and I.

Sample 1

3 1
2 1 3
2 2 3
2 3 3

2
1
2

Sample 2

3 2
2 1 3
2 2 3
2 3 3

2
1
0

Data Range and Hints

For all data, $1\le y,z,p\le 10^9,1\le T\le 10$, and it is guaranteed that $p$ is a prime number.