#include <bits/stdc++.h>
#define DMAX 1000000

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

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

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

int main()
{int i;
 long long int a,b;
 fin>>n;
 ciur();
 for(i=1;i<=n;i++)
     {fin>>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,j;
 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;
 long long 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;
     }
 fout<<x-ans<<'\n';
}