#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

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

const int Nmax = 1.066e6;
char prime[Nmax];
vi primes;

int main(void) {
  // freopen("pinex.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  memset(prime, 1, sizeof(prime));
  prime[0] = prime[1] = 0;
  for(int p = 2;  p <= Nmax; p++) {
    if (prime[p]) {
      primes.push_back(p);
      for(ll j = 1ll*p*p; j <= (ll)Nmax; j += p) {
        prime[j] = 0;
      }
    }
  }

  int m;
  ll a, b;
  fin >> m;
  while(m--) {
    fin >> a >> b;
    vi divs;
    for(auto p: primes) {
      if (b%p == 0) { divs.push_back(p); }
      while (b % p == 0) { b /= p; }
      if (!b) { break; }
    }
    ll result = 0;
    // cout << "prime divs:\t" << divs.size() << endl;
    rep(i, 1<<(divs.size())) {
      ll prod = 1;
      int sgn = 1;
      rep(j, divs.size()) {
        if (i & (1<<j)) {
          sgn *= -1;
          prod *= divs[j];
        }
      }
      result += 1ll*sgn*(a / prod);
    }
    fout << result << "\n";
  }
  return 0;
}