#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int a,b,nr,n,sol,i,d,t,f[1000010],f1[50010],x[50010],v[50010],w[50010],k,j;
void bkt(int pas){
    sol=1;
    if(pas>1){
        if((pas-1)%2==1){
            for(i=1;i<pas;i++)
                sol*=w[x[i]];
            nr-=(a/sol);
        }else{
            for(i=1;i<pas;i++)
                sol*=w[x[i]];
            nr+=(a/sol);
        }
    }
    for(int i=x[pas-1]+1;i<=n;i++)
        if(f1[i]==0){
            f1[i]=1;
            x[pas]=i;
            bkt(pas+1);
            f1[i]=0;
        }
}
int main(){
    for(i=2;i<=1000000;i++)
        if(f[i]==0){
            v[++k]=i;
            for(j=i*2;j<=1000000;j+=i)
                f[j]=1;
        }
    fin>>t;
    for(;t--;){
        fin>>a>>b;
        n=1;
        for(d=1;v[d]<=b;d++)
            if(b%v[d]==0)
                w[++n]=v[d];
        nr=a;
        bkt(1);
        fout<<nr<<"\n";
    }
    return 0;
}