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

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;i++)
     if(y%EC[i]==0)
        {V[++cate]=EC[i];
         while(y%EC[i]==0)
               y/=EC[i];
        }
 if(y)
    V[++cate]=y;
 ///acum prob in sine
 int nr,p1,ans=0;
 for (int i = 1;i < (1 << cate);i++)
        {
            nr = 0;
            p1 = 1;
            for (int 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);
}