#include <bits/stdc++.h>
#define InFile "pinex.in"
#define OutFile "pinex.out"
#define DMAX 1000010

using namespace std;

FILE *fin=fopen(InFile,"r");
FILE *fout=fopen(OutFile,"w");

int V[DMAX];
int n,cate;
bool C[DMAX];
vector <int> EC;

void ciur();
void pie(int a,int b);

int main()
{int i,a,b;
 fscanf(fin,"%d",&n);
 ciur();
 for(i=1;i<=n;i++)
     {fscanf(fin,"%d%d",&a,&b);
      pie(a,b);
     }
 return 0;
}
void ciur()
{int i,j;
 EC.push_back(2);
 for(j=4;j<DMAX;j+=2)
     C[j]=1;
 for(i=3;i*i<DMAX;i+=2)
     if(!C[i])
        {EC.push_back(i);
         for(j=i*i;j<DMAX;j+=i)
             C[j]=1;
        }
 for(i=1001;i<DMAX;i+=2)
     if(!C[i])
        EC.push_back(i);

}
void pie(int x,int y)
{int i,cate=0;
 for(i=0;EC[i]*EC[i]<=y && y>1;i++)
     if(y%EC[i]==0)
        {V[++cate]=EC[i];
         while(y%EC[i]==0)
               y/=EC[i];
        }
 if(y>1)
    V[++cate]=y;
 int nr,p1,ans=0;
 for(i= 1;i<(1<<cate);i++)
     {nr=0;
      p1=1;
      for(j=0;j<cate;j++)
          if(i&(1<<j))
             {p1*=V[j+1];
              nr++;
             }
      if(nr%2)
         ans+=x/p1;
         else
         ans-=x/p1;
     }
 fprintf(fout,"%d\n",x-ans);
}