#include<fstream>
#include<cmath>
using namespace std;
int fact[50],nrf;

inline void descompune(long long val){
       int i=3; nrf=0;
       while (i<=sqrt(val)){
              i+=2;
               if (val%i==0) {fact[++nrf]=i; while (val%i==0&&val>1) val/=i; }
          }
       if (val%2==0) {fact[++nrf]=2; while (val%2==0&&val>1) val/=2; }
       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,pos=1,solc=1,unu=0; 
            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;
    for (i=1; i<=n; ++i){
        long long a,b;
         fin>>a>>b;
          descompune(b);
         fout<<a-neprime(a)<<"\n";
         }
  return(0);
}