#include<bits/stdc++.h>
using namespace std;

int i,j,t,prim[1000005],nr,fact[50],m,k;
long long a,b,rs,aux;
bool viz[1000005],c[1000005];

int main()
{
  ifstream cin("pinex.in");
  ofstream cout("pinex.out");

  ios_base::sync_with_stdio(0); cin.tie(0);

  for(i=2;i<=1e6;++i)
  if(!c[i]) for(prim[++nr]=i,j=i+i;j<=1e6;j+=i) c[j]=1;

  for(cin>>t;t;--t)
  {
    cin>>a>>b; rs=m=0;

    for(i=1;i<=nr && prim[i]*prim[i]<=b;++i)
    if(b%prim[i]==0)
    {
      fact[++m]=prim[i];
      while(b%prim[i]==0) b/=prim[i];
    }

    if(b>1) fact[++m]=b;

    for(i=1;i<(1<<m);++i)
    {
      for(aux=1,k=j=0;j<m;++j)
      if(i&(1<<j)) ++k,aux*=fact[j+1];

      if(k&1) rs+=a/aux; else rs-=a/aux;
    }

    cout<<a-rs<<'\n';
  }

 return 0;
}