题目大意：
告诉你一个数n，求满足φ^x(n)=1的x。
思路：
首先我们可以发现满足φ(n)=1的数只有2，也就是说你得到最终的结果，最后一步肯定是φ(2)。
同时，可以发现φ(φ(2^k))=φ(2^(k-1))，因为1~2^k中间有且仅有奇数与2^k互质，个数是2^(k-1)个。
φ是个积性函数，也就是说φ(n)=φ(p1^q1)*φ(p2^q2)*...*φ(pm^qm)。
对于只有一种质因数的n， φ(n)=φ(p^q)=p^q*(1-1/p)=(p-1)*(p^q-1)。
因此我们可以发现，每次φ下去的时候都会往里面加若干个质因数2，而对于偶数，每次会消掉一个质因数2。
由于我们最后得到答案都要经过φ(2)，原问题转化为可以消掉多少个2，也就是总共会产生多少个2。
预处理出每个质因数最后能分解出多少个2，累加起来就是总共要消灭的2的个数。
预处理的时候可以用类似于线性筛的方法做。
注意如果一开始就没有质因数2，那就要多花一步来得到一个2。
#include<cstdio>
#include<cctype>
typedef long long int64;
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int P=,N=;
int f[P],prime[N],cnt;
inline void pret() {
f[]=;
for(register int i=;i<P;i++) {
if(!f[i]) {
prime[cnt++]=i;
f[i]=f[i-];
}
for(register int j=;j<cnt;j++) {
if(i*prime[j]>=P) break;
f[i*prime[j]]=f[i]+f[prime[j]];
if(!(i%prime[j])) break;
}
}
}
int main() {
pret();
for(register int T=getint();T;T--) {
int64 ans=;
for(register int m=getint();m;m--) {
const int p=getint(),q=getint();
ans+=(int64)f[p]*q;
if(p==) ans--;
}
printf("%lld\n",ans);
}
return ;
}