#include <iostream>
#include <fstream>

using namespace std;

typedef long long ll;

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

const int NMAX = 1e6;

ll a, b, sub, op[100];
ll n, i, s, j, nr, k, m;
ll p[80000], d[100], nrd, nrp=78498;
bool seen[NMAX + 10];

void calc () {
  ll pro = 1;
  for(int j = 1; j <= k; j++)
    pro *= d[op[j]];
  sub += a/pro;
}

void solve (ll p) {
  if(p == k + 1)
    calc();
  else {
    for (ll i = op[p - 1] + 1; i <= nrd; i++) {
      op[p] = i;
      solve(p + 1);
    }
  }
}

int main () {
  for(int i = 2; i <= 1e6; i++)
    if(seen[i] == 0) {
      nr++;
      p[nr] = i;
      for(int j = 2; j * i <= 1000000; j++)
        seen[i * j] = 1;
    }

  in >> m;
  while (m) {
    in >> a >> b;
    nrd = 0;
    nr = 1;
    while(b > 1 && nr <= nrp) {
      k = 0;
      while(b % p[nr] == 0) {
        b /= p[nr];
        k = 1;
      }

      if(k == 1) {
        nrd++;
        d[nrd] = p[nr];
      }
      nr++;
    }

    if(b > 1) {
      nrd++;
      d[nrd] = b;
    }

    s = a;
    bool p = 0;
    for(int i = 1; i <= nrd; i++) {
      k = i;
      sub = 0;
      solve(1);

      if(p == 0) {
        s -= sub;
        p = 1;
      }else {
        s += sub;
        p = 0;
      }
    }

    out << s << "\n";
    m--;
  }

  in.close();
  out.close();
  return 0;
}