#include <stdio.h>
#include <vector>

using ll = long long;

ll pinex( ll a, ll b ) {
  std::vector<ll> primes; {
    int d = 2;
    while( d * (ll)d <= b ){
      if( b % d == 0 ){
        primes.push_back( d );
        while( b % d == 0 )
          b /= d;
      }
      d++;
    }

    if( b > 1 )
      primes.push_back( b );
  }

  ll ret = 0;
  for( int mask = (1 << (int)primes.size()); mask--; ){
    ll prod = 1;
    for( int i = 0; i < (int)primes.size(); i++ )
      if( mask & (1 << i) )
        prod *= primes[i];
    
    ret += (a / prod) * (__builtin_popcount(mask) % 2 == 0 ? +1 : -1);
  }

  return ret;
}

int main() {
  FILE *fin = fopen( "pinex.in", "r" );
  FILE *fout = fopen( "pinex.out", "w" );

  int t;
  for( fscanf( fin, "%d", &t ); t--; ){
    ll a, b;
    fscanf( fin, "%lld %lld", &a, &b );
    fprintf( fout, "%lld\n", pinex( a, b ) );
  }

  fclose( fin );
  fclose( fout );
  return 0;
}