Home => ProblemSet => [HAOI2012] 外星人
2261: [HAOI2012] 外星人
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
艾莉欧在她的被子上发现了一个数字 N，她觉得只要找出最小的 x 使得，φx(N)=1。根据这个 x 她就能找到曾经绑架她的外星人的线索了。当然，她是不会去算，请你帮助她算出最小的 x。
Input
第一行一个正整数 test，接下来 test 组数据每组数据第一行一个正整数 m，接下来 m 行每行两个正整数 pi,qi。
φx(N) 表示嵌套 x 次，不是幂。
φx(N) 表示嵌套 x 次，不是幂。
Output
输出 test 行，每行一个整数，表示答案。
Sample Input Copy
1
2
2 2
3 1
Sample Output Copy
3
HINT
