#include <bits/stdc++.h>
using namespace std;

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

int main()
{
  long long m;

  fin >> m;
  for (long long i = 1; i <= m; i++)
  {
    long long a, b;
    fin >> a >> b;

    vector<long long> divPrim;

    for (long long div = 2; div <= b; div++)
      if (b % div == 0)
      {
        divPrim.push_back(div);
        while (b % div == 0)
          b /= div;
      }

    long long res = 0, size = divPrim.size(), steps = 1 << size;
    for (long long i = 1; i < steps; i++)
    {
      long long temp = 1, cnt = 0;
      for (long long p = 0; p < size; p++)
        if (i & (1 << p))
          temp *= divPrim[p], cnt++;

      if (cnt % 2 != 0)
        res += a / temp;
      else
        res -= a / temp;
    }

    fout << a - res << "\n";
  }

  return 0;
}