#include <stdio.h>
#include <string.h>

#define maxP 1000001
#define maxD 62501
#define maxNP 78499
#define maxDB 21

char p[maxD];
int np[maxNP];
int d[maxDB];

int main()
{
    int M;
    long long A,B;

    freopen("pinex.in","r",stdin);

    scanf("%d",&M);

    memset(p,0,sizeof(p));
    memset(np,0,sizeof(np));

    for(int i=1;((i*i)<<2)+(i<<2)+1<=maxP;++i)
        if((p[i>>3]&(1<<(i&7)))==0)
            for(int j=((i*i)<<1)+(i<<1);(j<<1)+1<=maxP;j+=(i<<1)+1)
                p[j>>3]|=(1<<(j&7));

    np[++np[0]]=2;
    for(int i=1;(i<<1)+1<=maxP;++i)
        if((p[i>>3]&(1<<(i&7)))==0)
            np[++np[0]]=(i<<1)+1;

    freopen("pinex.out","w",stdout);

    long long sol;
    for(;M--;)
    {
        scanf("%lld%lld",&A,&B);

        memset(d,0,sizeof(d));
        for(int i=1;i<=np[0]&&B!=1;++i)
            if(B%np[i]==0)
            {
                d[++d[0]]=np[i];
                while(B%np[i]==0) B/=np[i];
            }
        if(B!=1) d[++d[0]]=B;

        int powB=(1<<d[0]);
        sol=A;
        for(int i=1;i<powB;++i)
        {
            long long p=1;
            int b=0;
            for(int cnt=1,j=i;j;j>>=1,++cnt)
                if(j&1) p*=d[cnt],++b;

            if(b&1) p*=-1;
            sol+=A/p;
        }

        printf("%lld\n",sol);
    }

    return 0;
}