#include<stdio.h>
#include<math.h>

bool x[1000001];
long long int p[500000],nr[500000],s=0,pos=1,pos2=1;
long long int a,b;

FILE *fin,*fout;

void add(long long int position,long long int val,bool sign)
{
        for(long long int i=position+1;i<pos2;i++)
        {
            if(val/nr[i]!=0)
            {
                if(sign==1)
                {
                    s+=(val/nr[i]);
                    add(i,val/nr[i],0);
                }
                else
                {
                    s-=(val/nr[i]);
                    add(i,val/nr[i],1);
                }
            }
            else
            {
                break;
            }
        }

}

int main()
{
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    int m;
    for(long int j=2;j<=1000000;j++)
        {
            if(x[j]==0)
            {
                p[pos]=j;
                pos++;
                for(long int k=2;k*j<=1000000;k++)
                {
                    x[k*j]=1;
                }
            }
        }
    fscanf(fin,"%d",&m);
    for(int i=0;i<m;i++)
    {
        fscanf(fin,"%lld %lld",&a,&b);
        pos2=1;
        if(b==1)
        {
            fprintf(fout,"%d",a);
        }
        else
        {
        int sq=sqrt(b)+1;
        for(int j=1;j<pos&&p[j]<=a&&p[j]<=sq;j++)
        {
            if(b%p[j]==0)
            {
                while(b%p[j]==0)
                {
                    b/=p[j];
                }
                nr[pos2]=p[j];
                pos2++;
            }
        }
        if(b!=1)
        {
            nr[pos2]=b;
            pos2++;
        }
        add(0,a,1);
        fprintf(fout,"%lld",a-s);
        if(i!=m-1)
        {
                    fprintf(fout,"\n");
        }
        }
        s=0;
    }
}