记录编号	383726	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]外星人	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.864 s
提交时间	2017-03-16 11:04:31	内存使用	34.65 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>

#define int long long
using namespace std;

typedef long long LL;

using namespace std;
typedef bitset<64> bt;

void read(int &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = (x<<3)+(x<<1)+c-'0';
    flag?x=-x:x;
}

const int N = static_cast<int>(1e6+20);

int v[N],p[N/2],phi[N],tot,id[N],s[N];

int f(int x) {
	if(s[x]) return s[x];
	if(x == 1) return 0;
	return s[x] = f(phi[x])+1;
}

void calc_phi() {
	phi[1] = 1;
	for (int i = 2; i < N; i++) {
		if(!v[i]) p[++tot] = i,phi[i] = i-1;
		for (int j = 1; j <= tot; j++) {
			if(p[j]*i >= N) break;
			v[i*p[j]] = 1;
			if(i%p[j] == 0) {
			  phi[i*p[j]] = phi[i]*p[j];
			  break;
			} else phi[i*p[j]] = phi[i]*(p[j]-1);
		}
	}
	for (int i = 1; i <= tot; i++) id[p[i]] = i;
	for (int i = 1; i < N; i++) s[i] = f(i);
//	for(int i = 17; i <= N; i *= 17)
//	 cout<<i<<" "<< f(i) <<"\n";

}

int n;
LL ans;

LL calc() {
	int p,q;
	read(p); read(q);
	if(p == 2) return q;
	if(p == 3) return q+1;
	return s[p] + (q-1)*(s[p]-1);
}

void work() {
//	for (int i = 1; i <= 1000; i++)
//	 cout<<f(p[i]) <<" "<<calc(p[i])<<"\n";
	read(n);
	ans = -n+1;
	 for (int i = 1; i <= n; i++)
	   ans += calc();
	printf("%lld\n",ans);
}

 main() {
	freopen("alien.in","r",stdin);freopen("alien.out","w",stdout);
	calc_phi();
	int test; read(test);
	while(test--)
	work();
  	return 0;
}