#include <iostream>
#include <vector>

#define NMAX 1000000
#define PMAX 20

using namespace std;

char ciur [ NMAX + 1 ] ;
vector <int> prime ;

void precalculare () {
  int i, j;
  for (i = 2 ; i * i <= NMAX ; i++ ) {
    if (ciur[i] == 0 ) {
      prime.push_back(i) ;
      for (j = 2 * i ; j <= NMAX ; j+=i )
        ciur[j] = 1 ;
    }
  }
}

long long Primeb (int a, int b ) {
  int mask, i, j ;
  long long rez, prod ;
  vector <int> primeb ;
  for (i = 0 ; i < prime.size() ; i++ )
    if (b % prime[i] == 0 ) {
      primeb.push_back(prime[i]) ;
      printf ("%d ", prime[i] ) ;
    }
  int lim = (1 << primeb.size() ) ;
  rez = 0 ;
  for (mask = 1 ; mask < lim ; mask++ ) {
    prod = 1 ;
    for (j = 0 ; j < primeb.size() ; j++ ) {
      if ( ( mask & (1 << j) ) == (1 << j)  )
        prod *= 1LL * primeb[j] ;
    }
    if (__builtin_popcount(mask) % 2 == 0 )
      rez -= 1LL * a / prod ;
    else
      rez += 1LL * a / prod ;
  }
  return rez ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("pinex.in", "r" ) ;
  fout = fopen ("pinex.out", "w" ) ;
  int n, a, b, i ;
  precalculare () ;
  fscanf (fin, "%d", &n ) ;
  for (i = 0 ; i < n ; i++ ) {
    fscanf (fin, "%d%d", &a, &b ) ;
    fprintf(fout, "%lld\n", 1LL * a - Primeb( a, b ) ) ;
  }
  return 0;
}