#include<fstream>
#include<math.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long i,j,a,b,m;
int v[1000001],prim[1000001],factori[1000001],nrprim;
void erat(){
   int i,j;
   for (i=4;i<=1000000;i+=2) v[i]=1;
   nrprim++;
   prim[nrprim]=2;
   for (i=3;i<=1000000;i++)
    if (v[i]==0){
      nrprim++;
      prim[nrprim]=i;
      for (j=2*i;j<=1000000;j+=i)
        v[j]=1;
    }
}
void solve(long long a,long long b){
    long long sol,i,j,prod,exp;
    int nr,t=0;
    nr=0;
    while(b>1){
        nr++;
        if (b%prim[nr]==0){
           t++;
           factori[t]=prim[nr];
           while(b%prim[nr]==0) b=b/prim[nr];
        }
        if (prim[nr]>sqrt(b) && b>1){
            t++;
            factori[t]=b;
            b=1;
        }
    }
   sol=a;
    for (i =1; i<(1<<t);i++) {
        exp=0;prod=1;
        for (j =0; j<t;j++)
            if ((1 << j) & i) {
                prod = prod * (long long)factori[j + 1];
                exp++;
            }
        if (exp%2==1) exp = -1;
           else exp = 1;
        sol = sol+exp*a/prod;
    }
    fout<<sol<<'\n';
}
int main(){
    erat();
    fin>>m;
    for (i=1;i<=m;i++){
        fin>>a>>b;
        solve(a,b);
    }
   fin.close();
   fout.close();
   return 0;
}