记录编号	56694	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]外星人	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.117 s
提交时间	2013-04-02 14:53:14	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXP=100001;//最大筛到十万
long long contain[MAXP]={0,1,0};//2显然包含一个2,为了偷懒把1赋成1,后面让2跑算法
void prime(void){//神奇筛法
	int i,j;
	for(i=2;i<=MAXP;i++){
		if(contain[i]) continue;//已经被计算过,无视掉
		contain[i]=contain[i-1];//计算它本身
		for(j=2;i*j<=MAXP;j++){
			if(contain[j]) contain[i*j]=contain[i]+contain[j];
		}
	}
}
void work(void){
	int m;
	scanf("%d",&m);
	int i,p,q;
	long long sum=0;
	bool flag=false;
	for(i=0;i<m;i++){
		scanf("%d%d",&p,&q);
		if(p==2) flag=true;//是奇数
		sum+=contain[p]*q;
	}
	if(flag) cout<<sum<<endl;
	else cout<<sum+1<<endl;
}
int main(){
	freopen("alien.in","r",stdin);
	freopen("alien.out","w",stdout);
	prime();
	int test;
	scanf("%d",&test);
	for(int i=0;i<test;i++) work();
	return 0;
}