#include <cstdio>
#include <vector>
#include <bitset>
#define tip long long
#define MA 1000000000000000001
#define MB 1000000000001
#define NP 1000000

using namespace std;

/*ifstream f("pinex.in");
ofstream g("pinex.out");*/

bitset<NP> Ciur;
vector<tip> Primes;
vector<tip> Div;
int T;
tip A,B;

void GenPrimes();
tip Solve(tip,tip);

int main() {
    GenPrimes();
    //f >> T;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&T);
    for (;T;--T) {
        //f >> A >> B;
        //g << Solve(A,B) << '\n';
        scanf("%lld",&A);scanf("%lld",&B);
        printf("%lld\n",Solve(A,B));
    }
    //f.close();g.close();
    return 0;
}

void GenPrimes() {
    for (tip i=2;i<NP;i++)
        if (!Ciur[i]) {
            Primes.push_back(i);
            for (tip j=i*i;j<NP;j+=i) Ciur[j]=1;
        }
}

tip Solve(tip A,tip B) {
    Div.clear();
    tip C=B;
    for (tip i=0;i<Primes.size() && C>1;i++) {
        if (C%Primes[i]==0) {
            Div.push_back(Primes[i]);
            while (C>1 && C%Primes[i]==0) C/=Primes[i];
        }
        if (Primes[i]*Primes[i]>C && C>1) {
            Div.push_back(C);
            C=1;
        }
    }
    C=Div.size();
    tip Comb=(tip)1<<C,ANS=0,Sign,Prod,k,c,i;
    for (i=1;i<Comb;i++) {
        Sign=0;Prod=1;
        for (k=1,c=0;k<Comb;k<<=1,++c)
            if (i&k) {
                ++Sign;
                Prod=1LL*Prod*Div[c];
            }
        if (Sign%2==1) Sign=1;
                  else Sign=-1;
        Prod=A/Prod;
        ANS+=1LL*Prod*Sign;
    }
    return (A-ANS);
}