# include <fstream>
# define DIM 1000010
# define DIV 78599
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool f[DIM];
int d1[DIV],d[DIV],e[2*DIM];
int q,t,k,k1,i,j,x,nd,ok,nr,r,a,b,s;
int main () {
    fin>>t;
    for(q=1;q<=t;q++){
        k=k1=i=j=x=nd=ok=nr=r=a=b=s=0;
        fin>>a>>b;
        for(i=2;i<=b;i++){
            if(f[i]==0){
                d1[++k1]=i;
                for(j=2*i;j<=b;j+=i)
                    f[j]=1;
            }
        }
        x=b;
        j=1;
        while(j<=k1&&x!=1){
            nr=0;
            while(x%d1[j]==0){
                x/=d1[j];
                nr++;
            }
            if(nr)
                d[++k]=d1[j];
            j++;
        }
        if(x>1)
            d[++k]=x;
        for(i=1;i<=a;i++){
            x=i;
            j=1;
            nd=0;
            ok=1;
            while(j<=k&&x!=1){
                nr=0;
                while(x%d[j]==0){
                    x/=d[j];
                    nr++;
                }
                if(nr){
                    if(nr==1)
                        nd++;
                    else
                        ok=0;
                }
                j++;
            }
            if(x>1)
                ok=0;
            if(ok){
                if(!(nd%2))
                    e[++r]=i;
                else
                    e[++r]=-i;
            }
        }
        for(i=1;i<=r;i++)
        for(i=1;i<=r;i++)
            s+=a/e[i];
        fout<<s<<"\n";
    }
    return 0;
}