#include <cstdio>

using namespace std;
int n,i,j,nrb,a[500000],t,nr,pm[1000009],NR=0;
long long sum=0,x,y,pp,b[500000],yy;

void prime()
{
   int i,j;

   for (i=1;(((i*i)<<1)+(i<<1))<=1000000;++i)
      if (( pm[i>>5] & (1<<(i&31)) )==0)
     {
         for ( j= (((i*i)<<1) + (i<<1));(j<<1)+1<=1000000;j+=(i<<1)+1)
            pm[j>>5]|=(1<<(j&31));

     }



}


int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);


    scanf("%d",&n);prime();
    a[++NR]=2;
    for(i=1;2*i+1<=1000000;++i)
       if(!(pm[i>>5] & (1<<(i&31)))) a[++NR]=i*2+1;

    for(t=1;t<=n;++t)
    {
        scanf ("%lld%lld",&x,&y);
        nrb=0;yy=y;sum=0;

        for(j=1;a[j]*a[j]<=y && yy && j<=NR;++j)
           if(yy%a[j]==0)
           {
              b[++nrb]=a[j];
              while(yy%a[j]==0)
              yy/=a[j];

           }

           if(yy>1) b[++nrb]=yy;

           for(i=1; i<(1<<nrb) ;++i)
           {
              pp=1LL;nr=0;
              for(j=0;j<nrb;++j)
              if( ((i>>j)&1)==1 )
              {
                 pp=1LL*pp*b[j+1];
                 ++nr;

              }


              if(nr%2==1) sum+=(x*1LL)/(1LL*pp);
              else  sum-=(1LL*x)/(1LL*pp);

           }

          printf("%lld\n",x-sum);

    }



    return 0;
}