#include<fstream>
#include<cmath>
#define maxn 1000000
using namespace std;
int fact[50],nrf,prime[100001],nrp;
bool viz[1000001];

inline void ciur(){
          nrp=1; prime[nrp]=2;
         for (int i=3; i<=maxn; i+=2)
          if (viz[i]==false){
                       prime[++nrp]=i;
                        for (int j=2; j<=maxn/i; ++j) viz[i*j]=true;
                  }       
}
inline void descompune(long long val){
       int i; nrf=0;
        for (i=1; prime[i]<=sqrt(val)&&i<=nrp; ++i)
         if (val%prime[i]==0){ fact[++nrf]=prime[i]; while (val%prime[i]==0&&val>1) val/=prime[i]; }
       if (val>1)fact[++nrf]=val;
}

long long neprime(long long val){
     long long nrsub=(1<<nrf)-1,i=0,rez=0;
      while (i<nrsub){
            ++i; long long aux=i,solc=1; int unu=0,pos=1;
            for (int j=1; j<=nrf&&aux!=0; ++j){
                if (aux&1==1) {solc*=fact[pos]; ++unu;}
                 aux=aux>>1; ++pos;
                 }
             if (unu%2==0) rez-=val/solc; else rez+=val/solc;
      }
  return(rez);
}           

int main(void){
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    int n,i; fin>>n; ciur();
    for (i=1; i<=n; ++i){
        long long a,b;
         fin>>a>>b;
          descompune(b);
         fout<<a-neprime(a)<<"\n";
         }
  return(0);
}