我们可以发现，phi(x)与x相比，相当于x的每个质因子-1后再分解质因数，添加到现有的质因子中，比如质因子13相当于将13变成12，然后分解成2*2*3，再将2的质数+2,3的指数+1，除了质因子2之外的所有质因子都满足这一性质，每次有一个质因子2相当于变成1，也就是没有了。那么我们可以将问题转化成一个大数，每个质因子分解到最后会分成多少个2，比如刚才的13，变成2*2*3，然后3变成2，那么13求phi到最后就是3个2，也就是消掉一个13需要求3次phi，如果我们可以处理出每个质数最后分解成多少个2，就可以解决问题。
求分解多少个2可以线性筛的时候处理，设w[i]代表i这个数分解成多少个2，那么如果i为质数，w[i]=w[i-1]，否则w[i*prime[j]]=w[prime[j]]+w[i]。开始现将w[2]设为1.
还有就是如果开始的大数是奇数的时候，我们需要将答案加1，因为第一次求phi不会有2这一项被消掉，第二次开始才会不断地消2，每个质数分解之后-1，一定会是偶数，所以每次都能产生至少一个新的2的质因子，这样就保证了这个算法的正确性。
/************************************************************** Problem: 2749 User: BLADEVIL Language: Pascal Result: Accepted Time:456 ms Memory:1104 kb ****************************************************************/ //By BLADEVIL var prime, w :array[0..100010] of longint; flag :array[0..100010] of boolean; procedure make; var i, j :longint; begin for i:=2 to 100000 do begin if not flag[i] then begin inc(prime[0]); prime[prime[0]]:=i; w[i]:=w[i-1]; if i=2 then w[i]:=1; end; for j:=1 to prime[0] do begin if prime[j]*i>100000 then break; w[prime[j]*i]:=w[i]+w[prime[j]]; flag[prime[j]*i]:=true; if i mod prime[j]=0 then break; end; end; end; procedure main; var i, j, k :longint; t :longint; n :longint; ans :int64; x, y :longint; f :boolean; begin read(t); for k:=1 to t do begin read(n); ans:=0; f:=false; for i:=1 to n do begin read(x,y); if x=2 then f:=true; ans:=ans+int64(w[x])*int64(y); end; if not f then ans:=ans+1; writeln(ans); end; end; begin make; main; end.