#include <stdio.h>
#define MAX_N 2000000
#define MAX_PRIME 200000
#define MAX_FACT 40
int primes[ MAX_FACT ];
int top;

//ar mai tb implementat un ciur pt descompunere si de bagat long long da mi-e lene
int card( int n , int x ) {
  return n / x;
}

int mypow( int baza , int exp , int acum ) {
    if( exp == 0 )
        return acum;
    else if( exp % 2 == 0 )
        return mypow( baza * baza , exp / 2 , acum );
    else
        return mypow( baza * baza , exp / 2 , acum * baza );
}

int query( int a , int b ) {
  int d , i , lim , j , bits , rez , prod;
  d = 2;
  top = 0;
  while( d * d <= b ) {
    if( b % d == 0 ) {
        primes[ top ] = d;
        top++;
    }
    while( b % d == 0 )
        b = b / d;
    d++;
  }
  if( b > 1 ) {
      primes[ top ] = b;
      top++;
  }

  lim = mypow( 2 , top , 1 );
  rez = a;
  for( i = 1 ; i < lim ; i++ ) {
      bits = 0;
      prod = 1;
      for( j = 0 ; j < top ; j++ )
          if( i & ( 1 << j ) ) {
              bits++;
              prod *= primes[ j ];
          }
      rez = rez + card( a , prod ) * mypow( -1 , bits % 2 , 1 );
  }
  return rez;
}

int main() {
    int m, a , b , i;
    FILE *fin = fopen( "pinex.in" , "r" );
    fscanf( fin , "%d" , &m );

    FILE *fout = fopen( "pinex.out" , "w" );
    for( i = 0 ; i < m ; i++ ) {
        fscanf( fin , "%d%d" , &a , &b );
        fprintf( fout , "%d\n" , query( a , b ) );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}