CX 是一家慕课公司的程序员。几天前，他因为用户数据泄露而背了黑锅。因此，他不得不开发一种加密算法，以下是他的天才构思。

首先，协议指定了一个素数模数 $M$，然后服务器生成一个私钥 $P$，并向客户端发送公钥 $Q$。这里 $Q = P^{-1}$，即 $P \times Q \equiv 1 \pmod M$。

加密公式：$encrypted\_data = raw\_data \times P \pmod M$

解密公式：$raw\_data = encrypted\_data \times Q \pmod M$

这确实有道理，然而，作为一名数论大师，你打算破解它。你已经截获了关于 $P, Q, encrypted\_data$ 的信息，而 $M$ 保持未知。如果你能解密它，输出 $raw\_data$，否则，对 CX 说 "shuanQ"。

输入格式

第一行包含一个整数 $T (T \le 20)$，表示测试用例的数量。每个测试用例：

一行包含三个整数 $P, Q, encrypted\_data$。$(1 < P, Q, encrypted\_data \le 2 \times 10^6)$

保证 $P, Q, encrypted\_data < M$。

输出格式

对于每个测试用例，打印一个整数 $raw\_data$，或者一个字符串 "shuanQ"。

样例

输入 1

2
5 5 5
6 6 6

输出 1

shuanQ
1