#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);
tip LgPow(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)LgPow(2,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*=2,++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);
}
tip LgPow(tip b,tip p) {
  tip x,r;
  for (x=b,r=1;p>0;p>>=1) {
    if ((p & 1) !=0)
        r=r*x;
    x=x*x;
  }
  return r;
}