#include <fstream>
using namespace std;

char Er[1000005];
long Prime[1000000];
long PrimCount;

long long DivB[1000];
long DivCount;

long NrBiti[5000];

long CountBiti(long i)
{
 long r = 0;
 while (i > 0)
  {
   r += (i & 1);
   i >>= 1;
  }
 return r;
}

void ComputeBiti(void)
{
 long i;
 for (i = 1;i < 5000;i += 1)
  {
   NrBiti[i] = CountBiti(i);
  }
}

void Erathostene(long N)
{
 Prime[0] = 2;
 PrimCount = 1;
 long i,j;
 for (i = 3;i <= N;i += 2)
  {
   if (Er[i] == 0)
     {
      Prime[PrimCount] = i;
      PrimCount += 1;
      for (j = (i << 1);j <= N;j += i)
       {
        Er[j] = 1;
       }
     }
  }
}

void ComputeDivB(long long B)
{
 DivCount = 0;
 long primpos = 0;
 while ((B > 1) && (Prime[primpos] * Prime[primpos] <= B))
  {
   if ((B % Prime[primpos]) == 0)
     {
      DivB[DivCount] = Prime[primpos];
      DivCount += 1;
      do
        {
         B /= Prime[primpos];
        }
       while ((B % Prime[primpos]) == 0);
     }
   primpos += 1;
  }
 if (B > 1)
   {
    DivB[DivCount] = B;
    DivCount += 1;
   }
}

long long NumberFromBiti(long B)
{
 long i;
 long long res = 1;
 for (i = 0;i < DivCount;i += 1)
  {
   if (B & 1)
     {
      res *= DivB[i];
     }
   B >>= 1;
  }
 return res;
}

long long Solve(long long A,long long B)
{
 ComputeDivB(B);
 long long Count[20];
 memset(Count,0,20 * sizeof(long long));
 long i,mi;
 mi = 1 << DivCount;
 for (i = 1;i < mi;i += 1)
  {
   Count[NrBiti[i]] += A / NumberFromBiti(i);
  }
 long long res = 0;
 for (i = 1;i <= DivCount;i += 1)
  {
   if (i & 1)
     {
      res += Count[i];
     }
    else
     {
      res -= Count[i];
     }
  }
 return A - res;
}

int main(void)
{
 fstream fin("pinex.in",ios::in);
 fstream fout("pinex.out",ios::out);
 Erathostene(1000000);
 ComputeBiti();
 long long M,A,B,i;
 fin >> M;
 for (i = 0;i < M;i += 1)
  {
   fin >> A >> B;
   fout << Solve(A,B) << "\n";
  }
 fin.close();
 fout.close();
 return 0;
}