#include <fstream>
using namespace std;

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

const int NMax = 1000000;
int X[30],N,M;
long long A,B,Sol,Produs = 1;
bool Prime[NMax + 5];
int Prim[80000],k;
int Factor[30];

void Sieve()
{
  for(int i = 2; i <= NMax; ++i)
  {
    if(Prime[i] == 0)
    {
      Prim[++k] = i;
      for(int j = i + i; j <= NMax; j+=i)
        Prime[j] = 1;
    }
  }
}

void Back(int k)
{
  for(int i = X[k-1] + 1;i <= N; ++i)
  {
    X[k] = i;

    Produs = Produs * Factor[X[k]];

    if(k % 2)
      Sol += A / Produs;
    else
      Sol -= A / Produs;
    if(k < N)
      Back(k + 1);

    Produs = Produs / Factor[X[k]];

  }
}

void Decompose(long long B)
{
    for(int i = 1; i <= k && 1LL*Prim[i] * Prim[i] <= B; ++i)
    {
      int e = 0;
      while(B%Prim[i] == 0)
      {
        B = B / Prim[i];
        e++;
      }
      if(e)
        Factor[++N] = Prim[i];
     }
     if(B != 1)
        Factor[++N] = B;
}

int main()
{
  Sieve();

  fin>>M;
  while(M--)
  {
    fin >> A >> B;
    N = 0;Sol = 0;
    Decompose(B);
    Back(1);
    fout << A - Sol << "\n";
  }

  return 0;
}