#include <bits/stdc++.h>
#define NMAX 100009
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool ciur[NMAX];
vector<int> sol;
long long int a,b,i,ct;
void era();
int m;
bool uz[NMAX];
int main()
{era();
 fin>>m;
 for(i=1;i<=m;i++)
    {
     fin>>a>>b;
     long long int cb=b;
     long long int res=0;
     vector<long long int>div;
     for(ct=0; sol[ct]*sol[ct]<=cb;ct++)
        {
         int cate=0;
         while( cb%sol[ct]==0)
                {cb/=sol[ct];
                cate++;
                }
          if(cate)
                div.push_back(sol[ct]);

        }

     if(cb!=1)
        div.push_back(cb);
     int j=div.size();
     for(ct=1;ct<(1<<div.size());ct++)
        {
         int nr=0;
         long long int prod=1;
         for(int j=0; j<div.size();j++)
             if( (1<<j )& ct )
                {nr++;
                 prod*=div[j];
                }
         if(nr%2==1)
             res+=a/prod;
             else
            res-=a/prod;
        }
    fout<<a-res<<'\n';
    }
    return 0;
}
void era()
{
  int i,j;
  for(i=2;i*i<NMAX;i++)
         if(!uz[i])
            for(j=i*i;j<NMAX;j+=i)
                uz[j]=1;
 for(i=2;i*i<NMAX;i++)
    if(!uz[i])
        sol.push_back(i);

}