#include <iostream>
#include <fstream>
#include <bitset>
#define RMAX 1000010LL
#define PMAX 78510LL

using namespace std;
typedef long long ll;

int q,nrp,nrprime;
int prime[PMAX];
ll a,b,sz,pr,ans;
ll p[30];
bool pa[30];
bitset<RMAX> prim;
void ciur(){
  prim[0]=prim[1]=1;
  for(int i=2;i<RMAX;i++)
    if(prim[i]==0){
      prime[++nrprime]=i;
      for(ll j=(ll)i*i;j<RMAX;j+=i)prim[j]=1;
    }
}

int main()
{
    ifstream f ("pinex.in");
    ofstream g ("pinex.out");
    f>>q; ciur();
    while(q--){
      f>>a>>b;
      sz=0;
      for(ll i=1;i<=nrprime;i++)
        if(b%prime[i]==0){
          p[++sz]=prime[i];
          while(b%prime[i]==0)b/=prime[i];
        }
      if(b!=1)p[++sz]=b;
      ans=0;
      for(int nrd=1;nrd<(1<<sz);nrd++){
        nrp=0;
        for(int bt=1,bi=1;bi<=sz;bt<<=1,bi++)
          pa[bi]=((nrd|bt)==nrd),
          nrp+=((nrd|bt)==nrd);
        pr=1;
        for(int i=1;i<=sz;i++)pr*=(pa[i])?p[i]:1;
        if(nrp%2)ans+=a/pr; else ans-=a/pr;
      }
      g<<a-ans<<'\n';
    }
    f.close ();
    g.close ();
    return 0;
}