#include<cstdio>
#include<iostream>
using namespace std;
int maxn=500001;
int n,m;
int p[500001],s[500001],pt=0,ph[500001];
long long ans=0;
int make()
{
	ph[1]=1;
	int N=maxn;
	int k;
	for(int i=2;i<N;i++)
	{
		if(s[i]==0)
		{
			p[++pt]=s[i]=i;ph[i]=ph[i-1];
		}
		for(int j=1;j<=pt&&(k=p[j]*i)<N;j++)
		{
			s[k]=k;
				ph[k]=ph[i]+ph[p[j]];
			if(i%p[j]==0) break;
		}
	}
	return 0;
}
int main()
{
	freopen("alien.in","r",stdin);
	freopen("alien.out","w",stdout);
	make();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int m,ma=0;
		scanf("%d",&m);
		long long a,b;
		cin>>a>>b;
		ans=b*ph[a]+(a!=2); 
		for(int j=1;j<m;j++)
		{
			cin>>a>>b;
			ans+=b*ph[a];
		}
		cout<<ans<<endl;
	}
	//printf("%d",ph[4]);
	return 0;
}