# include<stdlib.h>
# include<stdio.h>
# define FIN "pinex.in"
# define FOUT "pinex.out"
# define NMAX 1000000
using namespace std;
char prim [ NMAX ] ;
long long np [NMAX],dv[NMAX] ;
long long A,B,T;
void ciur()
{for ( int i=1; i<NMAX; i++ )
  prim [ i ] = 1;
 for(int i=2;i<NMAX;i++)
  if(prim[i])
    {for(int j=i+i;j<=NMAX;j+=i)
     prim[i]=0;
     np[++np[0]]=i;}
     }
void rez()
{long long nrdiv=0;long long sol;
for(int i=1;np[i]*np[i]<=B;i++)
 {if(B%np[i]==0)
     {while(B%np[i]==0) B=B/np[i];
         dv[++nrdiv]=np[i];}
         }
  if(B>1) {dv[++nrdiv]=B;B=1;}
  long long bin=1<<nrdiv;
sol=A;  
for(int i=1;i<bin;i++)
 {long long nr=0;long long rez=1;
  for (int j=0;j<nrdiv;j++)
   if((1<<j) & i) {rez=1LL*rez* dv[j+1];
                nr++;}
   if(nr%2) nr=-1;
   else nr=1;
   sol=sol+1LL*nr*A/rez;     
        }       
  printf("%lld\n",sol);      
     }     
int main()
{freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&T);
ciur();
for(;T;T--)
 {scanf("%lld %lld",&A,&B);
    rez();      
     }
    
    return 0;}