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