Source: Super League of Chinese College Students Algorithm Design 2022, Contest 2 by HDU.

Problem Description

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 \pmod M$.

Encryption formula: $encrypted_{data} = raw_{data} \times P \bmod M$

Decryption formula: $raw_{data} = encrypted_{data} \times Q \bmod 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.

Input

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$.

Output

In each case, print an integer $raw_{data}$, or a string shuanQ.

Sample

2
5 5 5
6 6 6

shuanQ
1