#include <iostream>
#include <stdio.h>

using namespace std;

#define MMAX 1000000
#define RADMMAX 80000

int vec[MMAX + 1];
int vec_prime[RADMMAX];

int main()
{
    FILE *fin, *fout;
    long long num_a, num_b, sum;
    int num_m, rez, poz, ind1, ind2, divi, ind, cmmmc, cnt, put;

    vec[0] = vec[1] = 1;
    for ( divi = 2; divi * divi <=  MMAX; divi++ ) {
      if ( vec[divi] == 0 ) {
        for ( ind = divi * divi; ind <= MMAX; ind += divi )
          vec[ind] = 1;
      }
    }
    poz = 0;
    for ( ind = 2; ind <= MMAX; ind++ ) {
      if ( vec[ind] == 0 ) {
        vec_prime[poz] = ind;
        poz++;
      }
    }
    for ( ind = 0; ind <= MMAX; ind++ )
      vec[ind] = 0;

    fin = fopen( "pinex.in", "r" );
    fscanf( fin, "%d", &num_m );
    fout = fopen( "pinex.out", "w" );

    for ( ind = 0; ind < num_m; ind++ ) {

      fscanf( fin, "%lld%lld", &num_a, &num_b );
      poz = ind1 = 0;
      divi = vec_prime[0];
      while ( divi * divi <= num_b ) {
        put = 0;
        while ( num_b % divi == 0 ) {
          num_b = num_b / divi;
          put++;
        }

        if ( put > 0 ) {
          vec[poz] = divi;
          poz++;
        }
        ind1++;
        divi = vec_prime[ind1];
      }
      if ( num_b > 1 ) {
        vec[poz] = num_b;
        poz++;
      }


      sum = 0;
      for ( ind1 = 1; ind1 < (1 << poz); ind1++ ) {
        cmmmc = 1;
        cnt = 0;
        for ( ind2 = 0; ind2 < poz; ind2++ ) {
          if ( ind1 & (1 << ind2) ) {
            cmmmc *= vec[ind2];
            cnt++;
          }
        }

        if ( cnt & 1 )
          sum += num_a / cmmmc;
        else
          sum -= num_a / cmmmc;
      }
      rez = num_a - sum;
      fprintf( fout, "%d\n", rez );

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