#P2350. [HAOI2012] 外星人

[HAOI2012] 外星人

题目描述

艾莉欧在她的被子上发现了一个数字 NN,她觉得只要找出最小的 xx 使得,φx(N)=1\varphi^x(N) = 1。根据这个 xx 她就能找到曾经绑架她的外星人的线索了。当然,她是不会去算,请你帮助她算出最小的 xx

输入格式

第一行一个正整数 test\mathrm{test},接下来 test\mathrm{test} 组数据每组数据第一行一个正整数 mm,接下来 mm 行每行两个正整数 pi,qip_i, q_i

其中 i=1mpiqi\displaystyle \prod_{i = 1}^{m} p_i^{q_i}NN 的标准分解形式。

\prod 为连乘

φx(N)\varphi^x(N) 表示嵌套 xx 次,不是幂

输出格式

输出 test\mathrm{test} 行,每行一个整数,表示答案。

1
2
2 2
3 1

3

提示

30%30\% 的数据,N106N \le 10^6

60%60\% 的数据,x100x \le 100

100%100\% 的数据,test50\mathrm{test} \le 501pi1051 \le p_i \le {10}^51qi1091 \le q_i \le {10}^9m2000m \le 2000

φ\varphi 为欧拉函数,φ(n)\varphi(n) 即小于等于 nn 的数中与 nn 互质的数的个数。

提示:$\varphi(\prod_{i=1}^mp_i^{q_i})=\prod_{i=1}^m(p_i-1)*p_i^{q_i-1}$。