#include<bits/stdc++.h>

 using namespace std;

 #define MAXN 100000

 #define LL long long

 int prime[],phi[MAXN+],tot,f[MAXN+];

 bool vis[MAXN+];

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 void getEular()

 {

     int i,j;

     phi[]=;tot=;

     for(i=;i<=MAXN;i++)

     {

         if(vis[i]==false)

         {

             prime[++tot]=i;

             phi[i]=i-;

         }

         for(j=;j<=tot&&prime[j]*i<=MAXN;j++)

         {

             vis[prime[j]*i]=true;

             if(i%prime[j]==)

             {

                 phi[prime[j]*i]=prime[j]*phi[i];

                 break;

             }

             phi[prime[j]*i]=phi[prime[j]]*phi[i];

         }

     }

 }

 int main()

 {

     freopen("alien.in","r",stdin);

     freopen("alien.out","w",stdout);

     int T,i,m,p,q,n;

     bool flag;

     LL ans;

     T=read();

     getEular();

     memset(f,,sizeof(f));//f[i]代表i需要phi多少次才能化为1.(也就是等于能phi多少个2.)

     f[]=-;

     for(i=;i<=MAXN;i++)f[i]=f[phi[i]]+;

     f[]++;f[]++;

     while(T--)

     {

         m=read();ans=;

         flag=false;//判断奇数时要加一.

         for(i=;i<=m;i++)

         {

             p=read();q=read();

             if(p==)flag=true;

             ans+=(LL)f[p]*q;

         }

         if(flag==false)ans++;

         printf("%lld\n",ans);

     }

     fclose(stdin);

     fclose(stdout);

     return ;

 }