#include <bits/stdc++.h>

using namespace std;

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

long long prim[150000],i,j,m,np,p,n,a,b,d[120000],poz;
bool ciur[1000005];
long long s;
void desc(int x)
{
    for (int i=1;prim[i]<=sqrt(x+1);i++)
      if (x%prim[i]==0)
      {
          d[++poz]=prim[i];
          while (x%prim[i]==0) x/=prim[i];
      }
    if (x>1) d[++poz]=x;
}

void prod(int u,int n)
{
    if (n==j)
    {
        if (j%2) s+=a/p; else s-=a/p;
        return;
    }
    for (int i=u+1;i<=poz;i++)
    {
        p*=d[i];
        prod(i,n+1);
        p/=d[i];
    }
    return;
}

int main()
{
    fin>>n;
    for (i=3;i*i<=1000005;i+=2)
        for (j=i*i;j<=1000005;j+=i<<1)
        ciur[j/2]=1;
    prim[++np]=2;
    for (i=1;i<=500008;i++)
    if (!ciur[i]) prim[++np]=i*2+1;
    for (i=1;i<=n;i++)
    {
        s=0;
        fin>>a>>b;
        poz=0;
        desc(b);
        for (j=1;j<=poz;j++)
        {
            p=1;
            prod(0,0);
        }
        fout<<a-s<<"\n";
    }
    return 0;
}