最早是根据 RSA 这个著名的密码学算法设计的题面，但由于没有提到怎么根据密钥加密数据，以及不希望使人产生会不会 RSA 算法影响会不会本题的错误印象，所以在题面里改名 ASR 算法。

然而本题面由于过于冗长可能导致选手不想读于是就被毙了，遂一气之下把能删的就删了，但又懒得改数据了，于是也许你们就会发现题面里输入 e,d 好像是莫名其妙的（明明可以直接输入一个乘积）。。。

不过我还挺喜欢这版题面（的前半部分）的，所以……

以下是原本的题面：

小 OMG 注意到小 NROT 最近似乎偷偷加入了反内卷协会，每天都会收到反内卷协会发送来信息。

身为内卷协会的一员，小 OMG 立马截获了小 NROT 从反内卷协会收到的信息。

然而很不幸的是，这些信息都进行了加密，因此为了实锤小 NROT 反内卷，小 OMG 需要破解这些加密信息。很快，小 OMG 就确定了小 NROT 所采用的加密方式是一个叫做 ASR 算法的加密算法。

在 ASR 加密算法中：

1. 小 NROT 会私密的选取两个不同的质数 $p,q$，并记 $n=pq,\varphi=(p-1)(q-1)$。
2. 然后，小 NROT 会选取一个 $\varphi+1$ 的因数 $e$，并记 $d=\frac{\varphi+1}{e}$。
3. 最后，小 NROT 会丢弃 $p,q,\varphi$，向所有人公开 $e,n$ 这两个数字，并将 $d$ 保密。
4. 之后，任何人（包括反内卷协会）可以使用 $e,n$ 把将要向小 NROT 发送的信息加密并发送给小 NROT，然后只有知道 $d$ 的小 NROT 才有可能对这一信息进行解密（即使别人截获了这些加密了的信息，只要他不知道 $d$，就很难进行解密）。

然而小 OMG 是不知道 $d$ 的，因此难以破解小 NROT 收到的加密信息——不过，以和小 NROT 组队卷大作业的名义，小 OMG 成功的混入了小 NROT 的宿舍，然后以生病借药为借口在翻小 NROT 的柜子的时候偷偷找到了 $d$，这样小 OMG 就已经能破解小 NROT 收到的加密信息了。

不过，身为内卷协会的一员，小 OMG 怎么可能仅满足于破解这些小 NROT 收到的加密信息呢：他还要还原出被小 NROT 丢弃的 $p$ 和 $q$！并以此向小 NROT 证明只有内卷才是前途光明的。

不过限于水平，小 OMG 发现自己不会这件事情，不肯善罢甘休的他找到了你，希望你能帮他解决这一问题，并承诺如果你能解决这一问题的话他就引荐你加入内卷协会。

另外，由于小 N 非常谨慎，在他接受反内卷协会的加密信息的 $k$ 天里，每天都可能会选取不同的 $p_i,q_i$ 并生成对应的 $n_i,e_i,d_i,(1\le i\le k)$。假定小 OMG 在这 $k$ 天里每天都能获取 $n_i,e_i,d_i$，因此他希望你也能发挥内卷精神，每天都还原出相应的 $p_i,q_i$！

需要注意的是，有时由于小 OMG 的失误，获取的 $n_i,e_i,d_i$ 不一定正确；这可能会导致以下结果;

1. 存在两个不同的质数 $p_i,q_i$，使得 $n_i=p_iq_i$，并且 $e_id_i=(p_i-1)(q_i-1)+1$，这时你应当向小 OMG 报告 $p_i,q_i$。
2. 存在两个正整数 $p_i,q_i$，使得 $n_i=p_iq_i$，并且 $e_id_i=(p_i-1)(q_i-1)+1$，但 $p_i$ 和 $q_i$ 为相同的质数，或者 $p_i,q_i$ 不同时为质数；这时，你仍然应当向小 OMG 报告 $p_i,q_i$，而小 OMG 会自行判断 $p_i,q_i$ 是否相同、是不是质数。
3. 不存在两个正整数 $p_i,q_i$，使得 $n_i=p_iq_i$，并且 $e_id_i=(p_i-1)(q_i-1)+1$；这时，你应当向小 OMG 报告 GG 。

可以证明，对于给定的 $n_i,e_i,d_i$，结果必定为其上三种情况中的恰好一种（特别的，结果 1. 和结果 2. 不可能同时出现）。