#include<fstream>
#include<bitset>
#define dim 1000004
using namespace std;


ifstream f("pinex.in");
ofstream g("pinex.out");
bitset<dim>ok;
int a,b,sol,ans,k,K,n,i,j;
long long  A[dim],prim[dim],nr,num;
bool x[dim];
void desc () {

    for(i=1;i<=K && prim[i]*prim[i]<=b ;++i) {

        if(b%prim[i]==0) {
            while(b%prim[i]==0){
                b/=prim[i];
            }
            A[++num]=prim[i];
        }
    }
    if(b>1) {
        A[++num]=b;
    }

}
void ciur  () {
    K=1;
    prim[K]=2;
    for(i=3;i<=dim;i+=2) {

        if(ok[i]==0) {

            prim[++K]=i;
            for(j=i+i;j<=dim;j+=i)
                ok[j]=1;
            ok[i]=1;
        }

    }
}
void afis() {
    int sol=1;
    int nr=0;
    for(int i=1;i<=num;++i){
        if(x[i]){
            ++nr;
            sol*=A[i];
        }
    }
    if(nr) {

        if(nr%2){
            ans+=a/sol;

        }
        else{
            ans-=a/sol;
        }
    }
}
void back(int k) {

    if(k>num) {
        afis();
        return ;
    }
    for(int i=0;i<=1;++i) {
        x[k]=i;
        back(k+1);
    }
}

int main (){
    ciur();
    f>>n;

    for(;n;--n) {

        f>>a>>b;
ans=0;
        desc();
        back(1);
        g<<a-ans<<"\n";

    }

    return 0;
}