感觉上，挺神的一道题。
原本是想找莫比乌斯反演做的，接着不知道为什么来到了这里，因为他们都是数论？
网上看了很久都没有非常看懂，可能是我太垃圾了了吧，但网上感觉讲懂的也不多。。于是就靠自己与师兄咯
首先，在做这题之前，我们要先读懂题，像我就看了半天没看懂，就是说给你一个数N，每一次你可以对他进行几次phi操作，也就是n=phi(n)，问你多少次操作后会变成1.
前置技能：1是一个神奇的数1*a=a 【废话
必备技能1：在phi函数中，只有phi(2)=1，换句话说，我们必须经过phi(2)才可以得到答案，同时，任意一个数*phi(2)都是他本身
选学技能1*：phi（2^t)一次操作后会变成phi(2^(t-1))
必备技能2：phi函数是一个积性函数，所以phi(x)=phi(a1^b1)*phi(a2^b2)......phi(an^bn)
必备技能3：phi(an^bn)=an^bn*(1-1/(an))=(an-1)*(an^bn-1)
必备技能4：在质数这个大家族中，只有2是偶数，其他都是奇数，所以技能3中的(an-1)肯定是一个偶数
当你点亮了技能点后，你就可以尝试做这道题了
根据技能1，我们可以知道，我们每一次操作至多消掉一个2的因子（不管别的，只看2）
然后根据技能4，在每一次操作后，我们都会至少加入一个2的因子。
所以，最后一步就是我们要把2消掉，加入最后已经没有2可以消了，那么说明游戏已经结束了，因为没有新的2生成，也没有旧的2要操作了。
换句话说，这道题就是在问我们，这些数可以生成多少个2！因为每一轮只能消掉一个2，所以轮数=2的个数
特别的，假如一开始的一步是没有2存在的，也就是说一开始的数没有2这个因子，那么我们花费的步数就要加1，因为第一步没能消掉2
然后因为一个数变换之后他还会变成(an-1)*(an^bn-1)的形态，后面只少了1，bn有多少，an可以创造出的2就要翻多少倍
至于如何就是an可以生成多少个2呢，这时候你就需要预处理了。
对于一个素数，他本身是没有2这个因子的，于是他会先变成phi(an-1)，也就是他生成的2是等于phi(an-1)的
对于别的数，有一条式子：f[i*prime[j]]=f[i]+f[prime[j]]。你想phi(i*prime[j])=phi(i)*phi(prime[j])，那么他们2的因子不就是累加起来的嘛，难不成两个数相乘因子数目相乘
于是这道题就做完了？耗时11:00~3:00，其中颓废1+h，估计花了1~2个小时吧
贴个代码吧：
#include<cstdio>
#include<cstring>
typedef long long LL;
const LL N=100000;
LL T,m;
bool ok[N+5];
LL f[N+5],pri[N+5],cnt=0;
LL p,q;
void prepare()
{memset(ok,true,sizeof(ok));cnt=0;f[1]=1;for (LL u=2;u<=N;u++){if (ok[u]==true) {pri[++cnt]=u;f[u]=f[u-1];}for (LL i=1;i<=cnt;i++){LL j=pri[i];if (u*j>N) break;ok[u*j]=false;f[u*j]=f[u]+f[j];if (u%j==0) break;}}
}
int main()
{prepare();scanf("%lld",&T);while (T--){scanf("%lld",&m);LL ans=1;while (m--){scanf("%lld%lld",&p,&q);if (p==2) ans--;//第一步就可以消2了ans=ans+q*f[p]; }printf("%lld\n",ans);}return 0;
}