#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long a,b;
bool pr[1000005];
int p[1000005], d[1000005];
int f=0;
long long nr;
void ciur()
{
    int i,j;
    for(i=2;i<=1000000;i++)
    {
        if(!pr[i])
            for(j=i+i;j<=1000000;j+=i)
        {
            pr[j]=1;
        }
    }
    for(i=2;i<=1000000;i++)
    {
        if(!pr[i])
            p[++f]=i;
    }
}
int k=0;
void fact()
{
    int i=1;
    while(b>1)
    {
      if(b%p[i]==0)
      {
          d[++k]=p[i];
          while(b%p[i]==0)
          {
              b=b/p[i];
          }
      }
      i++;
    }
}

void bk(long long x, long long y, long long s)
{
    if(x==k+1)
    {
        nr+=a/y*s;
        return;
    }
    bk(x+1,y,s);
    bk(x+1,y*d[x],-s);
}
int main()
{
    int i,n;
    fin>>n;
    ciur();
    for(i=1;i<=n;i++)
    {
       nr=0;
       k=0;
       fin>>a>>b;
       fact();
       bk(1,1,1);
       fout<<nr<<'\n';
    }
    return 0;
}