#include <cstdio>
#include <cstring>

char c[1000100];
int prime[100000];

void ciur()
{
    for(int d=2;d*d<=1000000;d++)
    {
        if(c[d]==0)
        {
            for(int f=2;f*d<=1000000;f++)
                c[d*f]=1;
        }
    }
    for(int i=2;i<=1000000;i++)
        if(c[i]==0)
            prime[++prime[0]]=i;
}

void getfact(long long x,long long v[100])
{
    for(int i=1;i<=prime[0]&&prime[i]<=x;i++)
    {
        if(x<=1000000)
            if(c[x]==0)
            {
                v[++v[0]]=x;
                return;
            }
        if(x%prime[i]==0)
            v[++v[0]]=prime[i];
        while(x%prime[i]==0)
            x/=prime[i];
    }
    if(x!=1)
        v[++v[0]]=x;
}

long long solve()
{
    long long a,b;
    scanf("%lld%lld",&a,&b);
    long long f[100];
    memset(f,0,sizeof(f));
    getfact(b,f);
    long long sum=0;
    for(int i=1;i<(1<<f[0]);i++)
    {
        int bs=0;
        long long prod=1;
        for(int b=0;(1<<b)<=i;b++)
        {
            if(i&(1<<b))
            {
                prod=prod*f[b+1];
                bs++;
            }
        }
        if(bs%2==1)
            sum+=a/prod;
        else
            sum-=a/prod;
    }
    return a-sum;
}


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