#include<fstream>
using namespace std;
ifstream f ("pinex.in");
ofstream g ("pinex.out");
int T,nr,nrb;
long long val,v[300],vec[200010],A,B;
int st[300];
bool viz[1000100];
void backt(int k){
    for(int i=st[k-1]+1;i<=nrb;++i){
        st[k]=i;
        long long prod=1;
        for(int i=1;i<=k;++i){
            prod*=v[st[i]];
        }
        if(k%2) val=val+A/prod;
        else val=val-A/prod;
        if(k!=nrb) backt(k+1);
    }
}
int main()
{
    for(int i=2;i<=1000000;++i){
        if(!viz[i]){
            vec[++nr]=i;
            for(int j=2;i*j<=1000000;++j)
                viz[i*j]=1;
        }
    }
    f>>T;
    for(int i=1;i<=T;++i){
        f>>A>>B;
        int k=1;
        nrb=0;
        val=0;
        while(vec[k]*vec[k]<=B&&B!=1){
            if(B%vec[k]==0){
                v[++nrb]=vec[k];
                while(B%vec[k]==0){
                    B/=vec[k];
                }
            }
            ++k;
        }
        if(B!=1) v[++nrb]=B;
        backt(1);
        g<<A-val<<'\n';
    }
}