#include<fstream>
#include<cmath>
#define lim 1000008
#include<bitset>
using namespace std;


ifstream f("pinex.in");
ofstream g("pinex.out");
int v[20],prim[lim],r,k,t;
long long x[20],SOL,A,B;
bitset<lim>ok;
void ciur () {
    prim[1]=2;
    k=1;
    for(int i=3; i<=lim ; i+=2  ) {

        if(!ok[i]){

            prim[++k]=i;

            for(int j=2*i;j<=lim;j+=i)
                ok[j]=1;

            ok[i]=1;
        }

    }

}
void descompune () {
    int i;
    r=0;
    long long w=sqrt(B);
    for(i=1; prim[i]<=w&& i<=k && B>1;i++){

        if(B%prim[i]==0){

            while(B%prim[i]==0)
                B/=prim[i];
            v[++r]=prim[i];
        }
    }
    if(B!=1)
        v[++r]=B;
}
void afis (){

    int nr=0;
    long long sol=1;
    for(int i=1;i<=r;i++)
        if(x[i]){
            ++nr;
            sol*=v[i];
        }
    if(nr){

        if(nr%2)
            SOL+=A/sol;
        else
            SOL-=A/sol;
    }
}
void back (int niv){

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

    f>>t;

    ciur();
    while ( t )  {
        SOL=0;
        f>>A>>B;
        descompune();
        back(1);
        g<<A-SOL<<"\n";
        --t;
    }

    return 0;
}