[HAOI2012]外星人

题目描述

![](https://cdn.luogu.org/upload/pic/1626.png)

输入输出格式

输入格式


![](https://cdn.luogu.org/upload/pic/1627.png) π为连乘

输出格式


输出test行,每行一个整数,表示答案。

输入输出样例

输入样例 #1

1
2
2 2
3 1

输出样例 #1

3

说明

30%的数据,N≤10^6 60%的数据,x≤100 100%的数据,test≤50,1≤pi≤10^5,1≤qi≤10^9 φ为欧拉函数,φ(N)即小于等于N的数中与N互质的数的个数, 提示:$$\varphi(\prod_{i = 1}^m p_i^{q_i}) = \prod_{i = 1}^m (p_i - 1)*p_i^{q_i-1}$$