Problem Background

2024-8-11 update: Added a new hack case.

Problem Description

You are required 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 \), find the smallest non-negative integer \( x \) such that \( xy \equiv z \pmod p \).
3. Given \( y, z, p \), find the smallest non-negative integer \( x \) such that \( y^x \equiv z \pmod p \).

Give it your best shot to win the prize!

Input Format

The input file contains multiple sets of data.

The first line contains two positive integers \( T \) and \( K \), representing the number of data sets and the query type (all queries within a test point are of the same type).

The following \( T \) lines each contain three positive integers \( y, z, p \), describing a query.

Output Format

The output file includes \( T \) lines.

For each query, output one line of answer.

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

Sample Input and Output

Sample Input #1

3 1
2 1 3
2 2 3
2 3 3

Sample Output #1

2
1
2

Sample Input #2

3 2
2 1 3
2 2 3
2 3 3

Sample Output #2

2
1
0

Sample Input #3

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

Sample Output #3

0
1
Orz, I cannot find x!
0

Notes

The test cases are divided into three categories, with the following proportions:

All data satisfy: \( 1 \leq y, z, p \leq 10^9 \), \( p \) is a prime number, \( 1 \leq T \leq 10 \).

见题面 Input 部分

见题面 Output 部分