#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
#define input "pinex.in"
#define output "pinex.out"
#define NMAX 1000005
using namespace std;

ifstream fin(input);
ofstream fout(output);

bool prime[NMAX];
int fprime[NMAX / 10];
int factB[NMAX / 10];
long long A, B, M;

void Ciur()
{
  fill(prime + 2, prime + NMAX, 1);
  for(int i = 2; i <= NMAX ; i++)
  {
    if(prime[i])
    {
      for(int j = i + i ; j <= NMAX ; j += i)
        prime[j] = false;
      fprime[++fprime[0]] = i;
    }
  }
}

void solve()
{
  int d, lg;
  lg = d = 0;
  while(B > 1)
  {
    d++;
    if(B % fprime[d] == 0)
    {
      while(B % fprime[d] == 0)
        B /= fprime[d];
      factB[++lg] = fprime[d];
    }
    if(fprime[d] > sqrt(B) && B > 1)
    {
      factB[++lg] = B;
      B = 1;
    } 
  }
  long long ans = A;
  for(int i = 1; i < (1 << lg); i++)
  {
    long long nr = 0, prod = 1;
    for(int j = 0 ; j < lg; j++)
    {
      if((1 << j) & i)
      {
        prod = 1LL * prod * factB[j + 1];
        nr++;
      }
    }
    if(nr % 2)
      nr = -1;
    else
      nr = 1;
    ans = ans + 1LL * nr * A / prod;
  }
  fout << ans << "\n";

}

int main()
{
  Ciur();
  fin >> M;
  for(int i = 0 ; i < M ; i++)
  {
    fin >> A >> B;
    solve();
  }
  return 0;
}