Description

现在有两个用户由于巧合，拥有了相同的模数 $N$，但是私钥不同。设两个用户的公钥分别为 $e_1$ 和 $e_2$，且两者互质。明文消息为 $m$，密文分别为：

$$\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix}$$

现在，一个攻击者截获了 $c_1$ ，$c_2$，$e_1$，$e_2$，$N$，请帮助他恢复出明文 $m$ 。

Input Format

输入包含多组数据，第一行一个整数 $T$ 表示数据组数，保证 $1\le T\le 10^4$ 。接下来依次描述每组数据，对于每组数据：

• 一行包含五个正整数 $c_1$，$c_2$，$e_1$，$e_2$，$N$，保证 $2^{8}< N < 2^{63}$，$N$ 有且仅有两个素因子，其余数据严格按照上述RSA算法生成。

Output Format

对于每组数据，输出 $1$ 行：

• 一个非负整数 $m$，请选手务必在输出时保证 $0\le m<N$。答案 $m$ 保证与 $N$ 互质。

1
1502992813 2511821915 653507 57809 2638352023

19260817

Hint

版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。