#include <cstdio>
#include <bitset>
using namespace std;
FILE *fin=fopen("pinex.in", "r");
FILE *fout=fopen("pinex.out", "w");

long long 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(long long k, long long n){
    if(k>n){
        long long par=0;
        long long 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;
            }
        }
    }
    fscanf(fin, "%lld", &teste);
    for(int aux=1; aux<=teste; aux++){
        fscanf(fin, "%lld %lld", &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);
        fprintf(fout, "%lld\n", sol);
    }
}