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

using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
typedef long long ll;
const ll MxNrP=11, Bmax=1LL*1e12, MxSqrtB=1e6;

ll m, A, B, prim[MxSqrtB/5], b[MxNrP], s, nrb;
bool ciur[MxSqrtB+5];

void bkt(ll ind, ll p, ll nr1){
    if (ind==nrb){
        if (p==1)
            return;
        if (nr1%2==1)
            s+=A/p;
        else s-=A/p;
        return;
    }
    bkt(ind+1, p, nr1);
    bkt(ind+1, p*b[ind], nr1+1);
}

int main(){
    //ciur
    int nrp=0;
    for (ll i=2; i<=MxSqrtB; i++)
        if (!ciur[i]){
            prim[nrp++]=i;
            for (ll j=i*i; j<=MxSqrtB; j+=i)
                ciur[j]=1;
        }

    fin>>m;
    for (int i=0; i<m; i++){
        fin>>A>>B;
        
        int j=0; nrb=0;
        while (j<nrp){
            if (B%prim[j]==0){
                b[nrb++]=prim[j];
                while (B%prim[j]==0)
                    B/=prim[j];
            }
            j++;
        }
        if (B>1)
            b[nrb++]=B;
        bkt(0, 1, 0);
        fout<<A-s<<'\n';
        s=0;
    }
    return 0;
}