#include<stdio.h>
#include<math.h>

long long div[20],a,b,c[20],s,h=1;
int nrd;

void desc()
{
    int i,m;
    nrd=0;
    if(b%2==0)
    {
        while(b%2==0)
            b/=2;
        div[++nrd]=2;
    }
    m=sqrt(b);
    for(i=3;i<=m;i+=2)
    {
        if(b%i==0)
        {
            while(b%i==0)
                b/=i;
            div[++nrd]=i;
            if(b==1)
                break;
        }
    }
    if(b>1)
        div[++nrd]=b;
}

void back(int p)
{
    int i;
    if(p%2==0)
        s+=a/h;
    else
        s-=a/h;
    for(i=c[p-1]+1;i<=nrd;++i)
    {
        c[p]=i;
        h*=div[i];
        back(p+1);
        h/=div[i];
    }
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&a,&b);
        desc();
        s=0;
        for(i=1;i<=nrd;++i)
        {
            c[1]=i;
            h=div[i];
            back(2);
        }
        printf("%lld\n",a-s);
    }
    return 0;
}