艾利欧在她的被子上发现了一个数字 n，
她觉得只要找出最小的 x 使得，φ^x(n)=1
根据这个 x 她就能找到曾经绑架她的外星人的线索了
现在她给你这个数字 n 的标准分解形式，请你帮助她算出最小的 x
T 组数据
求出最小的 (x) ，使得 (varphi^x(n)=1) ？
这玩意儿怎么可能求得出来啊？
十分钟后……
艹！
显然，只有1和2的欧拉函数值为1,
因此题意为：给定 (n)，每次操作把 (n) 变换为 (varphi(n))，求最少几次操作后 (n=1)。
根据欧拉函数的定义，我们可以推出以下的式子：
[varphileft(prod_{i=1}^m {p_i}^{c_i}
ight)=prod_{i=1}^m (p_i-1) imes {p_i}^{c_i-1}
]
意味着每次操作会把上一次操作的答案中的最多一个 (2) 变为 (1)
所以我们只要求出每个质因子在操作过程中会产生多少个 (2) 即可
具体的过程为：我们设 (f(i)) 表示 (i) 在操作过程中会产生多少个 (2)
那么有如下转移方程：
- 当 (i) 为质数时，(f(i)=f(i-1))，因为质数进行操作后变为 (i-1) 而没有增加 (2) 的个数，因此应该和 (f(i-1)) 的答案相等。
- 当 (i=a imes b) 时，(f(i)=f(a)+f(b)) 因为 (i) 可以表示为两个数相乘，那么其 (2) 的次数应该为两者之和。
需要注意，当原数中没有因子 (2) 时，答案 +1
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int T,n,x,y;
ll ans=1;
ll phi[N],prim[N],prinum;
bool isprim[N];
void Ls()
{
phi[1]=1;
for(register int i=2;i<=100005;++i)
{
if(!isprim[i]) prim[++prinum]=i,phi[i]=phi[i-1];
for(register int j=1;j<=prinum&&prim[j]*i<=100005;++j)
{
isprim[prim[j]*i]=true;
phi[prim[j]*i]=phi[prim[j]]+phi[i];
if(!(i%prim[j])) break;
}
}
return;
}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
int main()
{
Ls();
read(T);
while(T--)
{
read(n);
for(register int i=1;i<=n;++i)
{
read(x);read(y);
if(x==2) ans--;
ans+=phi[x]*y;
}
printf("%lld
",ans);
ans=1;
}
return 0;
}