#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.2e6;
bitset<Nmax> prime;
vi primes;

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

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


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

  int m;
  ll a,b;
  fin >> m;
  while(m--) {
    fin >> a >> b;

    vector<ll> divs;
    for(auto p: primes) {
      if (b % p == 0) {
        divs.push_back(p);
        while(b > 1 && (b % p == 0)) { b /= p; }
      }
      if (b > 1 && 1ll*p*p > b) {
        divs.push_back(b);
        break;
      }
      if (b == 1) { break; }
    }

    ll answer = a;
    for(int msk=1; msk < (1<<divs.size()); msk++) {
      int sgn = 1;
      ll prod = 1;
      rep(j, divs.size()) {
        if (msk & (1 << j)) {
          sgn *= -1;
          prod = 1ll*prod*divs[j];
        }
      }
      answer = answer + 1ll * sgn * a / prod;
    }
    fout << answer << '\n';
  }


  return 0;
}