#include <iostream>
#include <stdio.h>
using namespace std;
bool ciur[1000001];
int nr_prim[78521], divizor[100];
int main() {
    FILE *fin, *fout;
    int m, prime_total=0, nr_divizori, CARDInal_suBmultime;
    long long i, j, produs, nr_prime_cu_b, mask, n, bit, a, b;

fin = fopen("pinex.in", "r");
fout = fopen("pinex.out", "w");
for(i=2;i<=1000000;i++){
ciur[i]=true;
}

//ciur++aflarea numerelor prime
for(i=2;i<=1000000;i++){
    if(ciur[i]==true)
    for(j=i*i;j+i<1000000;j+=i){
        ciur[j]=false;
    }
}

for(i=2;i<=1000000;i++){
    if(ciur[i]==true)
        nr_prim[++prime_total]=i;
}


fscanf(fin,"%d", &m);

for(j=1;j<=m;j++){
    fscanf(fin,"%lld%lld", &a, &b);
    nr_divizori=0;
    //aflu numarul de divizori ai lui b mai mic ca a;
    for(i=1;nr_prim[i]<=b&&i<=78520;i++){
        if(b%nr_prim[i]==0)
            divizor[nr_divizori++]=nr_prim[i];
    }
    divizor[nr_divizori]=1;
    //folosesc o masca pentru a gasi toate submultimile formate din multimea divizorilor lui a
    mask=1;
    n=1<<nr_divizori;
    nr_prime_cu_b=0;
    for(mask=1;mask<n;mask++){
        CARDInal_suBmultime=0;
        produs=1;
        for(bit=0;bit<nr_divizori;bit++){
            if(mask&(1<<bit)){
                produs=1*produs*divizor[bit];
                CARDInal_suBmultime++;
        }
        }
        if(CARDInal_suBmultime%2==1)
            nr_prime_cu_b+=a/produs;
        else
            nr_prime_cu_b-=a/produs;

        if(produs==0)
            printf("%lld", j);

    }

    fprintf(fout,"%lld\n", a-nr_prime_cu_b);
}



fclose(fin);
fclose(fout);

    return 0;
}