题目描述

题目背景

1977年，Ron Rivest、Adi Shamir和Leonard Adleman一起发明了RSA加密算法。一个简易版的算法流程如下。

• 首先随机选取两个大质数\(p,q\)，令\(N=pq\)。
• 令\(\Phi(x)\)表示比\(x\)小的和\(x\)互质的整数个数，可以证明\(\Phi(N)=(p-1)(q-1)\)。
• 随机选取一个与小于\(\Phi(N)\)且与\(\Phi(N)\)互质的整数\(e\)，计算其逆元\(d\)，也就是满足\(ed\equiv 1\mod \Phi(N)\)的唯一的\(d\)。
• 对外界公布\(e,N\)但不公布\(p,q,d\)。
• 当有人想要加密一个消息\(m\)的时候，首先需要保证\(gcd(m,N)=1\)，然后他会计算\(c\equiv m^e\mod N\)。
• 如果你需要解密，则根据费马小定理我们有\(c^d\mod N\equiv c^{ed}\mod N\equiv m\)。
• 费马小定理是对于任意\(N\)和与\(N\)互质的\(a\)： \[a^{\Phi(N)}\equiv 1\mod N.\]

题目内容

灰灰在监听名飞与大猪比的通信，名飞和大猪比使用RSA算法进行加密。
灰灰截获了五个整数\(N,e_1,e_2,c_1,c_2\)，你可以看作是两个对于同一个消息\(m\)的加密。具体来说他们满足
\[
\left\{
\begin{aligned}
&gcd(e_1,e_2)=1\\
&m^{e_1}\equiv c_1\mod N\\
&m^{e_2}\equiv c_2\mod N
\end{aligned}
\right.
\]

现在，数学不好的灰灰想让你帮他解出\(m\)。
总共有\(q\)组询问，每次都会给出一组\(N,e_1,e_2,c_1,c_2\)，你需要回答所有的询问。
虽然可以，但尽量不要尝试对\(N\)做质因数分解

输入输出格式

输入格式

第一行一个整数\(q\)，表示询问组数。
之后\(q\)行，每行五个整数\(N,e_1,e_2,c_1,c_2\)，表示一组询问。

输出格式

一共\(q\)行，每行一个整数\(m\)，输出的\(m\)需要在\([0,N-1]\)中。

样例

样例输入1

3
15 5 7 8 2
15 3 5 4 4
15 5 7 2 8

样例输出1

8
4
2

样例解释1：

对于第一组询问：
\[\left\{
\begin{aligned}
8^5=8\mod 15\\
8^7=2\mod 15
\end{aligned}
\right.\]

数据范围

对于所有数据：\(1\leq q\leq 10^4\), \(1\leq N\leq 10^{18}\), 保证所有的数都是使用RSA生成的。