#include <stdio.h>
#define MAXP 1000000
#define MAXF 14
#define MAXK 80000

char p[MAXP + 1]; //0=prim, 1=compus
int prime[MAXK];
long long fact[MAXF];
int maxk;

void ciur() {
  int i, div, k = 0;

  for ( div = 2; div <= MAXP; ++div ) {
    if ( p[div] == 0 ) {
	  prime[k++] = div;
	  for ( i = div + div; i <= MAXP; i += div ) {
		p[i] = 1;
	  }
	}
  }
  maxk = k;
}

long long A;

long long mult( int k ) { //nr de numere divizibile cu k <= A
  return A / k;
}

long long sol, d = 1;
int nr1;

void backtrack( int currentF, int nrf ) { //backtracking pentru divizori (nrf = nr factori primi)
  if ( currentF == nrf ) {
	if ( d > 1 ) {
	  if ( nr1 % 2 == 0 ) {
        sol -= mult( d );
      } else {
	    sol += mult( d );
      }
	}
  } else {
	backtrack( currentF + 1, nrf );
	d *= fact[currentF];
	++nr1;
	backtrack( currentF + 1, nrf );
	d /= fact[currentF];
    --nr1;
  }
}

int main() { 
  FILE *fin = fopen( "pinex.in", "r" );
  FILE *fout = fopen( "pinex.out", "w" );
  int t, k, f, p;
  long long B; //nr de numere <= A, prime cu B 

  fscanf( fin, "%d", &t );
  ciur();
  while ( t-- ) {
	fscanf( fin, "%lld%lld", &A, &B );
    k = f = 0;
	while ( prime[k] * prime[k] <= B && k < maxk ) {
	  p = 0;
	  while ( B % prime[k] == 0 ) {
		B /= prime[k];
		p = 1;
	  }
	  if ( p ) {
		fact[f++] = prime[k];
	  }
	  ++k;
	}
    if ( B > 1 ) {
      fact[f++] = B;
	}
	backtrack( 0, f );
    fprintf( fout, "%lld\n", A - sol );
    sol = 0;
  }
  fclose( fin );
  fclose( fout );
  return 0;
}