#include <cstdio>
#include <cstring>
#define Max 1000001

int pr[80000],k,f[22],d,x[22];

void ciur()
{
    bool p[Max];
    memset(p,0,sizeof(p));
    int i=2;
    while(i<=1000)
    {
        while(p[i])i++;
        for(int j=i*i;j<Max;j+=i)p[j]=1;
        i++;
    }
    for(int i=2;i<Max;i++)
    if(p[i]==0)pr[++k]=i;
}

void desc(long long n)
{
    int i=1;
    d=0;
    while(i<=k && pr[i]*pr[i]<=n)
    {
        if(n%pr[i]==0)
        {
            f[++d]=pr[i];
            while(n%pr[i]==0)n/=pr[i];
        }
        i++;
    }
    if(n!=1)f[++d]=n;
}

void pinex(long long a)
{
    int nr=0,i;
    long long s=0,p=1;
    memset(x,0,sizeof(x));
    while(x[d+1]==0)
    {
        i=1; while(x[i]){x[i]=0; nr--; p/=f[i]; i++;}
        x[i]=1; p*=f[i]; nr++;
        if(x[d+1]==0)
        if(nr%2)s+=a/p; else s-=a/p;
    }
    printf("%lld\n",a-s);
}

int main()
{
    int t;
    long long a,b;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld %lld",&a,&b);
            desc(b);
            pinex(a);
        }
    return 0;
}