Description

Now there are two users who, by coincidence, have the same modulus $N$ but different private keys. Let their public keys be $e_1$ and $e_2$, and they are coprime. The plaintext message is $m$, and the ciphertexts are:

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

Now, an attacker has intercepted $c_1$, $c_2$, $e_1$, $e_2$, and $N$. Please help him recover the plaintext $m$.

Input Format

The input contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases, and it is guaranteed that $1\le T\le 10^4$ . Then each test case is described as follows:

• One line contains five positive integers $c_1$, $c_2$, $e_1$, $e_2$, $N$. It is guaranteed that $2^{8}< N < 2^{63}$, $N$ has exactly two prime factors, and the other values are generated strictly according to the RSA algorithm described above.

Output Format

For each test case, output $1$ line:

• A non-negative integer $m$. Please make sure that $0\le m<N$ when outputting. It is guaranteed that the answer $m$ is coprime with $N$.

1
1502992813 2511821915 653507 57809 2638352023

19260817

Hint

Copyright Information

From the 2018 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5