#include<fstream>
#include<math.h>
#include<iostream>

#define maxprim 1000000
#define nrmaximprime 90000
using namespace std;

int nrprime[nrmaximprime],N,x[nrmaximprime];
bool viz[maxprim];
long long sol,A,produs,B,p[nrmaximprime];

void ciur() {

    int i,j;
    nrprime[0]=1;
    nrprime[1]=2;
    for(i=3;i<=maxprim;i+=2) {
        if(viz[i]==0){
            nrprime[0]++;
            nrprime[nrprime[0]]=i;
            for(j=i;j<=maxprim;j+=i)
                if(viz[j]==0)
                    viz[j]=1;
        }
    }

}

void obtinere_div_primi() {

    int i=0;
    N=0;

    for(i=1;i<=nrprime[0] && B>1;i++) {
        if(B%nrprime[i]==0) {
            N++;
            p[N]=nrprime[i];
            while(!(B%nrprime[i]))
                B/=nrprime[i];
        }
    }
    if(B>1){
        N++;
        p[N]=B;
    }

}

void backtracking(int k) {

    int i;
    for(i=x[k-1]+1;i<=N;i++) {

        x[k]=i;
        produs*=p[x[k]];
        if(k%2==1)
            sol+=A/produs;
        else
            sol-=A/produs;

        if(k<N)
            backtracking(k+1);
        produs/=p[x[k]];
    }

}

int main() {

    ifstream in("pinex.in");
    ofstream out("pinex.out");
    int T;
    in>>T;
    ciur();
    while(T) {

        in>>A>>B;
        produs=1;
        sol=0;

        obtinere_div_primi();
        backtracking(1);

        out<<A-sol<<'\n';
        T--;
    }
    in.close();
    out.close();
    return 0;

}