#include <stdio.h>
#include <stdlib.h>
#define MAX 2000000
FILE *fin, *fout;
long long A, B, prod, rasp;
int divi[11], prime[150000];
char ciur[MAX+1];

void pinex(){
  rasp=0;
  int d=0, i, n=0, nr;
  while(prime[d]*prime[d]<=B){
    i=0;
    while(B%prime[d]==0){
      B/=prime[d];
      i++;
    }
    if(i)
      divi[n++]=prime[d];
    d++;
  }
  if(B>1)
    divi[n++]=B;
  for(d=1; d<(1<<n); d++){
    prod=1; nr=0;///explicatiile sunt in word
    for(i=0; i<n; i++)
      if( d&(1<<i) ){
        prod*=divi[i];
        nr++;
      }
    rasp+=(1+(nr%2==0)*(-2))*A/prod;
  }
}

int main(){
  int m, d=2;
  fin=fopen("pinex.in", "r");
  fout=fopen("pinex.out", "w");
  for(d=2; d*d<=MAX; d++)
    if(ciur[d]==0)
      for(m=d*d; m<=MAX; m+=d)
        ciur[m]=1;
  m=0;
  for(d=2; d<=MAX; d++)
    if(ciur[d]==0)
      prime[m++]=d;
  fscanf(fin, "%d", &m);
  while(m--){
    fscanf(fin, "%lld %lld", &A, &B);
    pinex();
    fprintf(fout, "%lld\n", A-rasp);
  }
  fclose(fin);
  fclose(fout);
    return 0;
}