#include<fstream>
#include<cmath>
#define ll long long
using namespace std;

int f[50],fp[80005];
bool prim[1000003];

ll solve(ll A,ll B){    
     ll nrfact=0, k=0, sol=A, nr, prod; 
     
     // Descompun in factori primi
     while(B>1){
          ++k;
          if(B % fp[k] == 0)
          {
            f[++nrfact] = fp[k];
            while(B % fp[k] == 0) B/=fp[k];     
          }   
       
       if(fp[k] > sqrt(B) && B>1)
       {
         f[++nrfact] = B;
         B = 0;            
       }  
     }
     
     int i,j;
     // Generez submultimile
     for(i=1; i<(1<<nrfact);++i)
     {
       nr = 0; prod = 1;
       for(j=0;j<nrfact;++j)
         if(i & (1<<j))
         {
           prod = 1LL * prod * f[j+1];
           ++nr;     
         }
       if(nr&1) nr=-1; else nr=1;
       
       sol = sol + 1LL * nr * A / prod;
     }
     
     return sol;   
     }

int main(){
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    int N,i,j; 
    ll A,B;
    
    // Precalculez numerele prime
    for(i=2;i<=1000000;++i)
      if(!prim[i])
      {
        for(j=2;j<=(1000000/i);++j)
          prim[i*j]=1;
        fp[++fp[0]]=i;
      }
    
    cin>>N;
    for(i=1;i<=N;++i)
    {
      cin>>A>>B;
      cout<<solve(A,B)<<'\n';                 
    }
    
 return 0;   
}