#include <fstream>
#include <cstring>
#define DIM 1000005
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long n,i,x,j,p[DIM],s[DIM],f[10000],y,t,sol,unu,k,a,b,tt;
bool v[DIM];
int main(){
    for(i=2;i<=DIM;i++){
        if(v[i]==0){
                p[++x]=i;
            for(j=2;j*i<=DIM;j++){
                v[i*j]=1;
            }
        }
    }
    fin>>tt;
    for(y=1;y<=tt;y++){
        fin>>a>>b;
        sol=0;n=0;
        for(i=1;i<=x && p[i]<=b;i++){
            if(b%p[i]==0){
                s[++n]=p[i];
            }
        }

        while(f[0]==0){
            t=n;
            while(f[t]==1){
                f[t]=0;
                t--;
            }
            f[t]=1;
            unu=0;k=1;
            for(i=1;i<=n;i++){
                if(f[i]==1){
                    unu++;
                    k*=s[i];
                }
            }
            if(unu%2==0){
                sol+=a/k;
            }
            else{
                sol-=a/k;
            }
        }
        fout<<sol<<"\n";
        memset(s,0,sizeof(s));
        memset(f,0,sizeof(f));
    }






    return 0;
}