#include<stdio.h>

#define plm long long
#define Mmax 78505
#define Pmax 1000005

int p[Mmax];
plm t,A,B;
bool e[Pmax];
plm nr_tot,cur,prod,sol,cnt,d[Mmax];

void ciur()
{
    for(int i=2;i<Pmax;++i)
        if (!e[i])
            {
            p[++p[0]]=i;
            for(int j=2*i;j<Pmax;j+=i)
                e[j]=1;
            }
    
}

plm primi(int x)
{
    d[0]=0;
    sol=A;
    
    for(int i=1;p[i]*p[i]<=x && i<=p[0];++i)
        if (x%p[i]==0)
            {
            d[++d[0]]=p[i];
            for(;x%p[i]==0; x/=p[i]);
            }
    if (x>1)
        d[++d[0]]=x;
        
    nr_tot=(1<<d[0]);
    for(plm i=1;i<nr_tot;++i)
        {
            cur=i;
            prod=1;
            cnt=0;
            for(int j=1;cur;cur/=2 , ++j)
                if (cur%2==1)   
                    {
                    prod=prod*d[j];
                    cnt=(cnt+1)%2;
                    }
                    
            sol+= (cnt*(-2)+1)*(A/prod);
        }
        
    return sol;
}

int main()
{
    ciur();
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%lld",&t);
    for(;t;--t)
        {
        scanf("%lld%lld",&A,&B);
        printf("%lld\n",primi(B));
        }
    return 0;
}