#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)
{
    //fprintf(fout,"%lld %lld %d %lld     %lld \n",position,val,sign,s,pos2);
    if(val!=0)
    {
        for(long long int i=position+1;i<pos2;i++)
        {
            if(val/nr[i]!=0)
            {
                            //fprintf(fout,"%lld %lld %d %lld \n",nr[i],i,from,val);
                            //fprintf(fout,"%lld \n",s);
                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;
                //fprintf(fout,"%lld \n",p[pos]);
                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;
        for(int j=1;j<pos;j++)
        {
            if(x[j]>a)
            {
                break;
            }
            if(b%p[j]==0||p[j]%b==0)
            {
                nr[pos2]=p[j];
                //fprintf(fout,"%lld \n",nr[pos2]);
                pos2++;
            }
        }
        //fprintf(fout,"%lld \n",pos2);
        add(0,a,1);
        fprintf(fout,"%lld",a-s);
        if(i!=m-1)
        {
                    fprintf(fout,"\n");
        }
        //fprintf(fout,"\n");
        s=0;
    }
}