#include <fstream>
#include <vector>
#define int long long

using namespace std;

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

const int DIVMAX = 1e6;
const int BITMAX = (1 << 10);
int cmmmc[BITMAX + 1];
int setbiti[BITMAX + 1];
bool ciur[DIVMAX + 1];
vector <int> prime;
vector <int> divs;

int gcd( int a, int b ){
  int r;
  while( b ){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

int lcm( int a, int b ){
  return a / gcd(a, b) * b;
}

void ciur_prime() {
  for( int i = 2; i * i <= DIVMAX; ++i )
    if( !ciur[i] )
      for( int j = i * i; j <= DIVMAX; j += i )
        ciur[j] = 1;
  for( int i = 2; i <= DIVMAX; ++i )
    if( !ciur[i] )
      prime.push_back(i);
}

signed main() {
  ciur_prime();
  int q, a, b, i, ans, put, n, j, mask;
  fin >> q;
  while( q-- ){
    fin >> a >> b;
    i = 0;
    while( i < prime.size() && prime[i] * prime[i] <= b ){
      put = 0;
      while( !(b % prime[i]) ){
        ++put;
        b /= prime[i];
      }
      if( put > 0 )
        divs.push_back(prime[i]);
      ++i;
    }
    if( b > 1 )
      divs.push_back(b);
    n = divs.size();
    cmmmc[0] = 1;
    setbiti[0] = ans = 0;
    for( i = 1; i < (1 << n); ++i ){
      for( j = 0; j < n; ++j )
        if( i & (1 << j) ){
          mask = i ^ (1 << j);
          cmmmc[i] = lcm(cmmmc[mask], divs[j]);
          setbiti[i] = setbiti[mask] + 1;
          break;
        }
      if( setbiti[i] % 2 == 1 )
        ans += (a / cmmmc[i]);
      else
        ans -= (a / cmmmc[i]);
    }
    fout << a - ans << "\n";
    divs.clear();
  }
  return 0;
}