#include <iostream>
#include<cstdio>
using namespace std;
long long divprimi[100];
const int N=1000001;
long long prim[N];
bool ciur[N];
void ciurr(){
  long long i,j;
  ciur[1]=true;
  for(i=2;i<=N;i++){
    if(ciur[i]==0){
      prim[++prim[0]]=i;
      for(j=i*i;j<=N;j+=i)
        ciur[j]=true;
    }
  }
}
long long rezolva(long long a,long long b){
  long long i;
  long long k=1;
  long long d=1;
  long long nrnp=0;
  divprimi[0]=0;
  while(k<=prim[0] && (long long)prim[k]*prim[k]<=b){
    d=prim[k];
    if(b%d==0){
      divprimi[++divprimi[0]]=d;
      while(b%d==0)
        b=(long long)b/d;
    }
    k++;
  }
  if(b>1){
    divprimi[++divprimi[0]]=b;
  }
  long long j;
  long long nringrup;
  long long m=1;
  for(i=1;i<(1<<(divprimi[0]));i++){
    nringrup=0;
    m=1;
    for(j=0;j<=divprimi[0]-1;j++){
      if((i&(1<<j))>0){
        nringrup++;
        m=(long long)m*divprimi[j+1];
      }
    }
    if(nringrup%2==1)
      nrnp+=(long long)a/m;
    else
      nrnp-=(long long)a/m;
  }
  return a-nrnp;
}
int main()
{
    FILE*fin,*fout;
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    long long m,i;
    ciurr();
    fscanf(fin,"%lld",&m);
    long long a,b;
    for(i=1;i<=m;i++){
      fscanf(fin,"%lld%lld",&a,&b);
      fprintf(fout,"%lld\n",rezolva(a,b));
    }
    return 0;
}