#include <fstream>
using namespace std;

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

const int MaxVal = 1000000;
int X[20],N,M;
long long A,B,Sol,P = 1;
int Factor[20];
bool Prime[MaxVal + 5];
int Prim[80000];

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

void Back(int k)
{
  for(int i = X[k-1] + 1; i <= N; ++i)
    {
      X[k] = i;
      P = P * Factor[X[k]];
      if(k%2)
        Sol += A / P;
      else
        Sol -= A / P;
      if (k < N)
        {
          Back(k+1);
        }
       P = P / Factor[X[k]];

    }
}

int main()
{
    fin >> M;
    Sieve();
    while(M--)
    {
      fin >> A >> B;
      N = 0;
      for(int i = 1; i <= Prim[0] && 1LL * Prim[i] * Prim[i] <= B; ++i)
      {
        int Nr = 0;
        while(B % Prim[i] == 0)
        {
          B = B / Prim[i];
          Nr++;
        }
        if(Nr)
          Factor[++N] = Prim[i];
      }
      if(B != 1)
        Factor[++N] = B;

      Sol = 0;
      Back(1);
      fout << A - Sol << "\n";
    }

    return 0;
}