#include<fstream>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int v[10001],k,prim[80001];
bool ciur[1000001];

int main(){
    int n,a,b;
    cin>>n;
    for(int i=2;i<=1000000;i++){
        if(ciur[i]==0)
        {
            prim[++k]=i;
            for(int j=2*i;j<=1000000;j+=i)
                  ciur[j]=1;
        }
    }
  while(n){
     cin>>a>>b;
     n--;
    long long bb=b;
    int nrd=0;
    for(int i=1;i<=k&&1ll*prim[i]*prim[i]<=bb;i++)
         if(bb%prim[i]==0){
             v[++nrd]=prim[i];
           while(bb%prim[i]==0)
              bb/=prim[i];
        }
      if(bb>1)
        v[++nrd]=bb;
        long long sol=0;
      /// generez submltimi ale lui nrd
      for(long long i=1;i<(1ll<<nrd);i++){
          int nr=0;
          long long p=1;
          for(int j=0;j<=40;j++)
              if((1&(1ll*i>>j))==1)
          {
              nr++;
              p*=v[j+1];
          }
          if(nr%2==0)
              sol-=a/p;
            else
                sol+=a/p;
      }
      cout<<a-sol<<"\n";
  }
}