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 , then the server generates a private key , and
sends the client a public key Q . Here .Q = P^-1 ,P ×Q ≡ 1 mod M
Encryption formula:e = r * P mod M
Decryption formula:r = e * 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 , and M keeps unknown. If you can decrypt it,
output r, else, say "shuanQ" to CX.
输入格式
First line has one integer T , indicating there are T test cases. In each case:
One line has three integers . ( P,Q，e)
It's guaranteed that
输出格式
In each case, print an integer r, or a string "shuanQ".