U137412 高斯的小宇宙

想必大家都听说过小高斯用高中数学必修五的知识爆锤小学老师的故事吧？现在，因为锤不过计算机，他来锤你了。

高斯挑战评测姬失败之后，无奈地承认人力和姬力还是有很大的差距的。但是他又把矛头对准了所有学计算机的！你！义不容辞！ 高斯要和你比拼算一些简单问题的能力。他要和你比算这些问题的能力： 1 a b 算$\gcd(a,b)$ 2 a b 算$lcm(a,b)$ 3 a 判断a是否为质数 4 a 算从1到a有多少个质数 5 a 求a的欧拉函数$\phi(a)$ 6 a p算出1-a在模p意义下的乘法逆元 7 a 算出1-a的欧拉函数 8 a 对a质因数分解 9 a p 算出a在模p意义下的乘法逆元

输入的第一行是一个整数$N$，表示高斯要跟你比赛$N$场。之后的$N$行，每行描述一个比赛，如上所述。

输出$N$行，第$i$行表示你对第$i$场比赛的答案。

数据范围： $1\le N\le 10$