#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long  m,t,prim[1000001],v[1000001],n;
long long rasp,j,i;
unsigned long long v2[25],a,b;
void bkt(int poz,unsigned 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;
            if(i*i<=1000000)
            {
                for(j=i*i; j<=1000000; j+=i)
                {
                    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;
}