#include <iostream>
#include <fstream>
#define LL long long int
#define MAXN 1000000
using namespace std;


LL A,B,sum,aux=1; int K,p[300000],P,M,f[50]; bool v[MAXN+5];

void gen_primes(){
    int i,j;
    for (i=2; i<=MAXN; i++)
        if (!v[i]){
            p[++P]=i;
            for (j=2*i; j<=MAXN; j+=i)
                v[j]=1;
        }
}

void comb(int cnt,int ind){
    if (cnt==0){
        sum+=A/aux;
        return;
    }

    if (K-ind+1>cnt)
        comb(cnt,ind+1);
    aux*=f[ind];
    comb(cnt-1,ind+1);
    aux/=f[ind];
}

int main(){
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    fin >> M;

    gen_primes();
    int i,k; LL res=0;
    for (k=1; k<=M; k++){
        fin >> A >> B;

        K=0; res=0;
        for (i=1; i<=P && 1LL*p[i]*p[i]<=B; i++)
            if (B%p[i]==0){
                f[++K]=p[i];
                while (B%p[i]==0) B/=p[i];
            }
        if (B!=1) f[++K]=B;

        for (i=1; i<=K; i++){
            sum=0;
            comb(i,1);
            if (i%2) res+=sum;
            else res-=sum;
        }

        fout << A-res << "\n";
    }

    return 0;
}