# include<stdlib.h>
# include<stdio.h>
# include<math.h>
# define FIN "pinex.in"
# define FOUT "pinex.out"
# define NMAX 1000000
using namespace std;
char prim [ NMAX ] ;
int np[80000],dv[200] ;
long long A,B,T;
void ciur()
{ for(int i=2;i<NMAX;i++)
  if(!prim[i])
    {for(int j=i+i;j<NMAX;j+=i)
     prim[i]=1;
     np[++np[0]]=i;}
     }
void rez()
{long long nrdiv=0;long long sol;
    long long i=0;
    while (B > 1) {
		i++;
        if (B % np[i] == 0) {
            dv[++nrdiv] = np[i];
            while (B % np[i] == 0)
                B /= np[i];
        }

        if (np[i] > sqrt(B) && 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;}