#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int nr1,nr,pr[100000],sol[100];
long long a,b,i,suma,div[100],m,j,hh,h,huh;
bitset <1000001> x;
void primi(long long z)
  {
      nr1=0;
      i=1;
      while(i<=nr && (long long)pr[i]*pr[i]<=z)
         {
             if(z%pr[i]==0)
               {
                   nr1++;
                   div[nr1]=pr[i];
                   while(z%pr[i]==0)
                      z=z/pr[i];
               }
            i++;
         }
      if(z>1)
       {
           nr1++;
           div[nr1]=z;
       }
  }
void modi(long long n,long long mm,long long poz,long long &sumi)
  {
     long long p=1;
     for(long long k=1;k<=mm;k++)
            p=p*div[sol[k]];
     if(mm%2==0)
        p=-p;
     sumi=sumi+a/p;
  }
void bkt(long long n,long long mm,long long poz,long long &sumi)
  {
      if(poz==mm+1)
         modi(n,mm,poz,sumi);
         else
         {
             for(long long i=1;i<=n;i++)
               {
                 int ok=1;
                 for(long long j=1;j<poz;j++)
                      if(sol[j]==i)
                         ok=0;
                 if(ok==1  && sol[poz-1]<i)
                    {
                      sol[poz]=i;
                      bkt(n,mm,poz+1,sumi);
                    }
               }
         }
  }
int main()
{

    for(i=2;i<=1000000;i++)
       x[i]=1;
    for(i=2;i<=1000;i++)
      {
          if(x[i]==1)
                for(j=i*i;j<=1000000;j=j+i)
                   x[j]=0;
      }
    nr=0;
    for(i=2;i<=1000000;i++)
      if(x[i]==1)
        {
            nr++;
            pr[nr]=i;
        }
    f>>m;
    for(hh=1;hh<=m;hh++)
      {
         suma=0;
         f>>a>>b;
         primi(b);
         for(h=1;h<=nr1;h++)
            {
               huh=0;
               bkt(nr1,h,1,huh);
               suma=suma+huh;
            }
          g<<a-suma<<'\n';
      }
    f.close();
    g.close();
    return 0;
}