You are required to design a calculator to perform the following three tasks:

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

Input

The input contains multiple test cases. The first line contains two positive integers $T$ and $K$, representing the number of test cases and the query type, respectively (for all data within a single test point, the query type is the same). The following $T$ lines each contain three positive integers $y, z, P$, describing a query.

Output

For each query, output the answer on a single line. For query types 2 and 3, if there is no $x$ that satisfies the condition, output "Orz, I cannot find x!". Note that there is a space between the comma and "I".

Examples

Input 1

3 1
2 1 3
2 2 3
2 3 3

Output 1

2
1
2

Input 2

3 2
2 1 3
2 2 3
2 3 3

Output 2

2
1
0

Input 3

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

Output 3

0
1
Orz, I cannot find x!
0

Constraints

For 20% of the data, $K = 1$. For 35% of the data, $K = 2$. For 45% of the data, $K = 3$. For 100% of the data, $1 \le y, z, P \le 10^9$, $P$ is a prime number, $1 \le T \le 10$.