#include <iostream>
#include <fstream>

using namespace std;

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

long long m,a,b;

bool isPrime[1000500];
int prime[1000500];
int pCount;

long long divs[1000500];
int dCount;

int mult[1000500];
int multCount;
long long sum;
int neg=1;

void write()
{
  for(int i=0;i<multCount;i++)
    cout<<mult[i]<<" ";
  cout<<"\n";
}

void addS()
{
  long long pow=1;
  for(int i=0;i<multCount;i++)
    pow=pow*divs[mult[i]-1];
  sum+=neg*(a/pow);
}



int main()
{
  fin>>m;
  for(int i=3;i<1000500;i+=2)
    isPrime[i]=true;
  for(int i=3;i*i<1000500;i+=2)
    for(int j=i*i;j<1000500;j+=i)
      isPrime[j]=false;
  for(int i=3;i<1000500;i++)
    if(isPrime[i])
    {
      prime[pCount]=i;
      pCount++;
    }
  for(int i=0;i<m;i++)
  {
    fin>>a>>b;
    long long c= b;
    dCount=0;
    sum=0;
    for(int i=2;i<=b&&i*i<=c;i+=(i==2)?1:2)
    {
      if(b%i!=0) continue;
      divs[dCount]=i;
      dCount++;
      while(b%i==0)
        b=b/i;
    }
    if(b!=1)
    {
      divs[dCount]=b;
      dCount++;
    }
    neg=1;
    for(int j=0;j<dCount;j++)
    {
      multCount=j+1;
      for(int l=0;l<multCount;l++)
        mult[l]=l+1;
      addS();
      while(true)
      {
        int l= multCount-1;
        mult[l]++;
        while(l>=0 && mult[l]>dCount-(multCount-l-1))
        {
          if(l>0)
            mult[l-1]++;
          l--;
        }
        if(l==-1)break;
        for(l++;l<multCount;l++)
          mult[l]=mult[l-1]+1;
     //   write();
        addS();
      }
      neg=-neg;
    }
    fout<<a-sum<<"\n";
  }
}