#include <fstream>
#include <vector>
#include <bitset>
#define tip long long
#define MA 1000000000000000001
#define MB 1000000000001
#define NP 1000010

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;
    for (;T;--T) {
        f >> A >> B;
        g << Solve(A,B) << '\n';
    }
    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];
        }
    C=Div.size();
    tip Comb=(tip)1<<C,ANS=0,Sign,Prod;
    for (tip i=1;i<Comb;i++) {
        Sign=0;Prod=1;
        for (tip k=1,c=0;k<Comb;k<<=1,++c)
            if (i&k) {
                ++Sign;
                Prod*=Div[c];
            }
        if (Sign%2==1) Sign=1;
                  else Sign=-1;
        Prod=A/Prod;
        ANS+=Prod*Sign;
    }
    return (A-ANS);
}