#include <bits/stdc++.h>
#define maxn 1000000

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long a, b, t;
vector<int> prime;
bitset<maxn + 5> ciur;
vector<long long> factori;

void Ciur()
{
  for(int i = 2;i <= maxn;++i)
    if(!ciur.test(i))
    {
      prime.push_back(i);
      for(int j = i;j <= maxn;j += i)
        ciur.set(j);
    }
}

void Solve()
{
  factori.clear();
  int pos = 0;
  while(b > 1)
  {
    if(b % prime[pos] == 0)
    {
      factori.push_back(prime[pos]);
      while(b % prime[pos] == 0)
        b /= prime[pos];
    }
    if(prime[pos] > sqrt(b) && b > 1)
    {
      factori.push_back(b);
      break;
    }
    ++pos;
  }

  long long sol = a;
  for(int i = 1;i < (1 << factori.size()); ++i)
  {
    long long nr = 0, prod = 1;
    for(int j = 0;j < factori.size();++j)
      if(i & (1 << j))
      {
        ++nr;
        prod = 1LL * prod * factori[j];
      }
    nr = (nr % 2 == 0) ? 1 : -1;
    sol = sol + 1LL * nr * (a / prod);
  }
  g<<sol<<'\n';
}

void Read()
{
  f>>t;
  Ciur();
  for(int i = 1;i <= t;++i)
  {
    f>>a>>b;
    Solve();
  }
  f.close();
  g.close();
}

int main()
{
  Read();
  return 0;
}