ShuanQ

CX is a programmer of a mooc company. A few days ago, he took the blame for leakage of users' data. As a result, he has to develop an encryption algorithm, here is his genius idea.

First, the protocol specifies a prime modulus $M$, then the server generates a private key $P$, and sends the client a public key $Q$. Here $Q = P ^ {-1},P \times Q \equiv 1 \mod M$.

Encryption formula: $encrypted\_{data} = raw\_{data} \times P \mod M$

Decryption formula: $raw\_{data} = encrypted\_{data} \times Q \mod M$

It do make sense, however, as a master of number theory, you are going to decrypt it.You have intercepted information about $P, Q, encrypted\_{data}$, and $M$ keeps unknown. If you can decrypt it, output $raw\_{data}$, else, say "shuanQ" to CX.

First line has one integer $T(T \leq 20)$, indicating there are $T$ test cases. In each case:

One line has three integers $P, Q, encrypted\_{data}$. ($1 < P, Q, encrypted\_{data} \leq 2 \times 10^6$)

It's guaranteed that $P, Q, encrypted\_{data} < M$.

In each case, print an integer $raw\_{data}$, or a string "shuanQ".

2
5 5 5
6 6 6

shuanQ
1

2022“杭电杯”中国大学生算法设计超级联赛（2）