#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

int teste, a, b, p, prim[1000002], NrFactoriPrimi, factor[1000002], sol, stiva[1000002];
bitset<1000002>ciur;

/// pentru a determina numărul de numere naturale mai
/// mici sau egale cu A şi prime cu B luam numarul total din care
/// scadem numerele divizibile cu un factor prim, apoi le adunam pe cele
/// divizibile cu 2 dintre ei, scadem pe cele cu 3 factori, etc


void calculeaza(int k, int n){
    if(k>n){
        int par=0;
        int divizor=1;
        for(int i=1; i<=n; i++){
            if(stiva[i]==1){
                par++;
                divizor*=factor[i];
            }
        }
        if(par%2==1){
            sol-=a/divizor;
        }else{
            sol+=a/divizor;
        }
    }else{
        for(int i=0; i<=1; i++){
            stiva[k]=i;
            calculeaza(k+1, n);
        }
    }
}

int main(){
    for(int i=2; i<=1000000; i++){
        if(ciur[i]==0){
            p++;
            prim[p]=i;
            for(int j=i+i; j<=1000000; j+=i){
                ciur[i]=1;
            }
        }
    }

    fin>>teste;
    for(int aux=1; aux<=teste; aux++){
        fin>>a>>b;
        NrFactoriPrimi=0;
        int bb=b;
        /// calculam factorii primi ai lui b
        /// pentru viteza, tinem factorii primi pana la sqrt(10^12) adica 10^6 intr un vector ciur
        for(int i=1; prim[i]!=0 && prim[i]<=b/prim[i] && bb != 1; i++){
            if(bb%prim[i]==0){
                NrFactoriPrimi++;
                while (bb%prim[i]==0) {
                    factor[NrFactoriPrimi]=prim[i];
                    bb/=prim[i];
                }
            }
        }
        if(bb!=1){
            NrFactoriPrimi++;
            factor[NrFactoriPrimi]=bb;
        }
        sol=0;
        calculeaza(1, NrFactoriPrimi);
        fout<<sol<<"\n";
    }
}