Background

In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed the RSA encryption algorithm. RSA is an asymmetric encryption algorithm, and its security depends on the difficulty of factoring very large integers. In other words, the harder it is to factor a very large integer, the more reliable RSA is. If someone finds a fast factoring algorithm, then the security of information encrypted with RSA will definitely drop a lot.

The basic idea of RSA is as follows:

• Generating the public key and private key
  1. Randomly choose two different large primes $p$ and $q$, and compute $N=p\times q$.
  2. By the property of Euler's totient function, compute $r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$.
  3. Choose a positive integer $e$ less than $r$ such that $e$ and $r$ are coprime. Then compute the multiplicative inverse $d$ of $e$ modulo $r$, satisfying $ed\equiv 1 \pmod r$.
  4. Destroy the records of $p$ and $q$. At this point, $(N,e)$ is the public key, and $(N,d)$ is the private key.
• Message encryption: First, convert the message $m$ into an integer $n$ that is less than $N$ and coprime with $N$, in a format agreed upon by both parties. If the message is too long, it can be split into several parts (this is what we call block encryption). Then each part is encrypted using:

$$n^{e}\equiv c\pmod N$$

• Message decryption: Decrypt using the key $d$:

$$c^{d}\equiv n\pmod N$$

Problem 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