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

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

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

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

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&a,&b);
        desc();
        s=0;
        back(0,1);
        printf("%d\n",a-s);
    }
    return 0;
}