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

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

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

void pinex()
{
  factori.clear();
  for(auto it : prime)
  {
    if(!(b % it)) factori.push_back(it);
    while(!(b % it)) b /= it;
    if(it > sqrt(b) && b > 1)
      factori.push_back(b), b = 1;
    if(b == 1)
      break;
  }

  long long rez = 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) ? -1 : 1;
    rez += 1LL * nr * (a / prod);
  }
  g<<rez<<'\n';
}

void Solve()
{
  f>>n;
  eras();  
  for(int i = 1;i <= n;++i)
    f>>a>>b, pinex();
}

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