#include <bits/stdc++.h>
#define L 1000005
#define S 14
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

bool ciur[L];
long long primes[S];

void init_ciur(){
  for (int d = 2; d * d < L; d++)
    if (!ciur[d])
      for (int i = d * d; i < L; i += d)
        ciur[i] = true;
}

void prime_decomp(long long x){
  int i = 1;
  for (long long d = 2; d * d <= x; d++)
    if (!ciur[d] && x % d == 0){
      while (x % d == 0)
        x /= d;
      primes[i++] = d;
    }
  if (x > 1)
    primes[i++] = x;
  primes[0] = i - 1;
}

int main(){
  init_ciur();
  int n;
  fin >> n;
  for (int i = 1; i <= n; i++){
    long long a, b, ans = 0;
    fin >> a >> b;
    prime_decomp(b);
    for (int mask = 1; mask < (1 << primes[0]); mask++){
      long long x = 1;
      int cnt = 0;
      for (int bit = 0; bit < primes[0]; bit++)
        if ((1 << bit) & mask){
          x *= primes[bit + 1];
          cnt++;
        }
      ans += 1LL * (cnt % 2 * 2 - 1) * (a / x);
    }
    ans = a - ans;
    fout << ans << "\n";
  }
  return 0;
}