#include <iostream>
#include <fstream>
#define int long long
using namespace std;
const int MAXA = 1e6;

ifstream fin( "pinex.in" );
ofstream fout( "pinex.out" );

char ciur[MAXA+1];
int prime[MAXA];
int diviz[MAXA];
signed main() {
  int m, i, j, k, nrdiv, mask, prod, nr, ans, a, b;
  ciur[0] = ciur[1] = 1;
  for( i = 2; i * i <= MAXA; i++ ) {
    if( ciur[i] == 0 ) {
      for( j = i * i; j <= MAXA; j += i )
        ciur[j] = 1;
    }
  }
  k = 0;
  for( i = 2; i * i <= MAXA; i++ ) {
    if( ciur[i] == 0 )
      prime[k++] = i;
  }
  fin >> m;
  for( i = 0; i < m; i++ ) {
    fin >> a >> b;
    nrdiv = 0;
    j = 0;
    while( j < k ) {
      if( b % prime[j] == 0 )
        diviz[nrdiv++] = prime[j];
      j++;
    }
    ans = 0;
    for( mask = 1; mask < ( 1 << nrdiv ); mask++ ) {
      prod = 1;
      nr = 0;
      for( j = 0; j < nrdiv; j++ ) {
        if( mask & ( 1 << j ) ) {
          prod = prod * diviz[j];
          nr++;
        }
      }
      if( nr % 2 == 0 )
        ans -= a / prod;
      else
        ans += a / prod;
    }
    fout << a - ans << "\n";
  }
  return 0;
}