2022 Hangdian multi school second session 1009 shuangq (Mathematics)

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×Q≡1modM.
Encryption formula: encrypted_data=raw_data×PmodM
Decryption formula: raw_data=encrypted_data×QmodM
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≤20), indicating there are T test cases. In each case:

One line has three integers P,Q,encrypted_data. (1<P,Q,encrypted_data≤2×106)

It's guaranteed that P,Q,encrypted_data<M.

Output

In each case, print an integer raw_data, or a string "shuanQ".

Sample Input

2

5 5 5

6 6 6

Sample Output

shuanQ

1

The main idea of the topic ：

For a given P And its inverse Q as well as enc, Seeking the cause P seek Q Of mod, And work out P*enc%mod

Ideas ：

For each pair PQ There is a unique prime factor M(M>P&&M>Q) bring P*Q-1==K*M（ The falsification is shown in the figure below ）, All you have to do is P*Q-1 Find out the prime factor of

  Code implementation ：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
typedef long long LL;
int main(){
	int t;
	cin>>t;
	while(t--){
		LL P,Q,enc,raw=-1;
		cin>>P>>Q>>enc;
		LL KM=P*Q-1,M;
		for(LL i=2;i*i<=KM;i++){
			if(KM%i) continue;
			while(KM%i==0) KM/=i;// Make sure that every time i All prime numbers  
			M=i;// It must be a prime number  
		}
		if(KM>1) M=KM;
		if(M>Q&&M>P){
			raw=enc*Q%M;
			cout<<enc*Q%M<<endl;
		}
		else puts("shuanQ");
	}
	return 0;
}