#include <cstdio>
#include <cmath>

using namespace std;

bool p[1009999];
long long v[100005];
long long d[100005];

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    long long nrp=0,t,a,b,sq,m;
    scanf("%lld",&t);
    for(long long i=2;i<=1000000;++i)
        {
            if(p[i]==0)
                {
                    v[++nrp]=i;
                    long long j=i;
                    while(j<=1000000)
                        {
                            j+=i;
                            if(j>1000000)
                                break;
                            p[j]=1;
                        }
                }
        }
    while(t--)
    {
        long long nrd=0,rez=0,miau=1;
        scanf("%lld %lld",&a,&b);
        p[1]=1;
        sq=sqrt(b);
        if(p[b]==0)
        {
            nrd=1;
            d[1]=b;
        }
        else{
        for(long long i=1;v[i]<=sq;++i)
        {
            if(b%v[i]==0)
                {
                    d[++nrd]=v[i];
                    while(b%v[i]==0)
                        b/=v[i];
                }
        }
        if(p[b]==0)
        {
            nrd++;
            d[nrd]=b;
        }
        }
        long long pt=1<<nrd;
        for(long long i=1;i<=pt-1;++i)
        {
            miau=1;
            long long ham=0;
            for(long long j=0;j<nrd;++j)
            {
                m=1<<j;
                if(m&i)
                {
                    miau*=d[j+1];
                    ham++;
                }
            }
            long long semn;
            if(ham%2==1)
                semn=1;
            else
                semn=-1;
            rez+=semn*(a/miau);
        }
        printf("%lld\n",a-rez);
    }
    return 0;
}