#include <iostream>
#include<cstdio>
using namespace std;
long long divprimi[20];
long long rezolva(long long a,long long b){
  int i;
  long long d=2;
  long long nrnp=0;
  divprimi[0]=0;
  while(d*d<=b){
    if(b%d==0){
      divprimi[++divprimi[0]]=d;
      while(b%d==0)
        b/=d;
    }
    d++;
  }
  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;
    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;
}