// This program was written by Mircea Rebengiuc
// on 17.08.2022
// for problem pinex

#include <stdio.h>
#include <ctype.h>

using ll = long long;

#define MAXP 20
#define MAXSQRT 1000000

FILE *fin, *fout;
ll div[MAXP];

// opmizare cu un factor de ln(MAXSQRT) ~= 13
char ciur[1 + MAXSQRT];
int primes[MAXSQRT];
int NPRIMES;

ll solve_testcase(){
  ll lim, x, d, ans = 0;
  int np, mask, semn, cp, i;

  fscanf( fin, "%lld%lld", &lim, &x );

  np = 0;
  i = 0;
  while( i < NPRIMES && primes[i] * primes[i] <= x ){
    d = primes[i];

    if( !(x % d) ){
      div[np++] = d;
      while( !(x % d) )
        x /= d;
    }

    i++;
  }
  if( x > 1 )
    div[np++] = x;

  for( mask = (1 << np) ; mask-- ; ){
    cp = mask;
    semn = 0;
    d = 1;
    for( i = 0 ; i < np ; i++ ){
      if( cp & 1 ){
        d *= div[i];
        semn ^= 1;
      }
      cp >>= 1;
    }

    ans += (semn * -2 + 1) * (lim / d);
  }

  return ans;
}

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

  int t, i, d;

  ciur[0] = ciur[1] = 1;
  for( d = 2 ; d * d <= MAXSQRT ; d++ )
    if( !ciur[d] )
      for( i = d * d ; i <= MAXSQRT ; i += d )
        ciur[i] = 1;

  NPRIMES = 0;
  for( i = 2 ; i <= MAXSQRT ; i++ )
    if( !ciur[i] )
      primes[NPRIMES++] = i;

  for( fscanf( fin, "%d", &t ) ; t-- ; )
    fprintf( fout, "%lld\n", solve_testcase() );

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