#include<cstdio>
#include<math.h>
using namespace std;
bool p[1000999];
long long v[100007];
long long d[100007];
long long nrp,t,a,b,sq,m;
void ciur()
{
    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) p[j]=1;
                        }
                }
        }
}
void inex(long long a, long long b)
{
    long long nrd=0,rez=0,prod=1;
        p[1]=1;
        sq=sqrt(b);
        for(long long i=1;v[i]<=sqrt(b);++i)
        {
            if(b%v[i]==0)
                {
                    d[++nrd]=v[i];
                    while(b%v[i]==0)
                        b/=v[i];
                }
        }
        if(b!=1)
        {
            nrd++;
            d[nrd]=b;
        }
        long long pt=1<<nrd;
        for(long long i=1;i<=pt-1;++i)
        {
            prod=1;
            long long num=0;
            for(long long j=0;j<nrd;++j)
            {
                m=1<<j;
                if(m&i)
                {
                    prod*=d[j+1];
                    num++;
                }
            }
            long long semn;
            if(num%2==1)
                semn=1;
            else
                semn=-1;
            rez+=semn*(a/prod);
        }
        printf("%lld\n",a-rez);
    }
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    scanf("%lld",&t);
   for(long long kpp=1;kpp<=t;kpp++)
    {
        scanf("%lld %lld",&a,&b);
        inex(a,b);
        //printf("%lld %lld\n",a,b);
    }
    return 0;
}