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

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

vector<long long> primes;
const long long prime_max = 1000000;

void getPrimes()
{
  bitset<1000001> vis(false);
  primes.push_back(2);
  for (long long i = 4; i <= prime_max; i += 2)
    vis[i] = true;

  for (long long i = 3; i <= prime_max; i += 2)
    if (vis[i] == false)
    {
      primes.push_back(i);
      for (long long j = i * i; j <= prime_max; j += i)
        vis[j] = true;
    }
}

int main()
{
  long long m;

  getPrimes();

  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 : primes)
      if (div > b)
      {
        break;
      }
      else if (b % div == 0)
      {
        divPrim.push_back(div);
        while (b % div == 0)
          b /= div;
      }

    if (b > 1)
      divPrim.push_back(b);

    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;
}