#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int m,t,i,prim[1000001],v[1000001],n,j;
long long rasp,v2[25],a,b;
void bkt(int poz,long long p,int nr)
{
    if(poz>m)
    {
        if(p==1)
        {
            return;
        }
        if(nr%2==0)
        {
            rasp-=a/p;
        }
        else
        {
            rasp+=a/p;
        }
        return;
    }
    bkt(poz+1,p*v2[poz],nr+1);
    bkt(poz+1,p,nr);
}
int main()
{
    f>>t;
    for(i=2;i<=1000000;i++)
    {
        if(prim[i]==0)
        {
            v[++n]=i;
            for(j=i*i;j<=1000000;j++)
            {
                prim[j]=1;
            }
        }
    }
    while(t--)
    {
        f>>a>>b;
        m=0;
        rasp=0;
        for(i=1;i<=n && v[i]*v[i]<=b;i++)
        {
            if(b%v[i]==0)
            {
                m++;
                v2[m]=v[i];
                while(b%v[i]==0)
                {
                    b/=v[i];
                }
            }
        }
        if(b!=1)
        {
            m++;
            v2[m]=b;
            b=1;
        }
        bkt(1,1,0);
        g<<a-rasp<<'\n';
    }
    return 0;
}