#include<cstdio>
int v[10001],v1[1000001];
char ciur[1000001];
int main()
{
 int m,f,a,b,d,cb,p,q,i,j,prod,k,s,nr,e,t;
 freopen("pinex.in","r",stdin);
 freopen("pinex.out","w",stdout);
 scanf("%d",&m);
 ciur[1]=1;
 e=0;
 for(d=2;d*d<=1000000;d++)
    {
     if(ciur[d]==0)
        {
         for(i=d*d;i<=1000000;i+=d)
             ciur[i]=1;
         v1[++e]=d;
        }
    }
 for(f=1;f<=m;f++)
    {
     scanf("%d%d",&a,&b);
     /*d=2;
     cb=b;
     q=0;
     while(cb!=1)
          {
           p=0;
           while(cb%d==0)
                {
                 cb/=d;
                 p=1;
                }
           if(p==1)
              v[++q]=d;
           d++;
          }*/
     /*q=0;
     for(i=1;i<=b;i++)
        {
         if(ciur[i]==0 && b%i==0)
            v[++q]=i;
        }*/
     q=0;
     t=1;
     while(t<=e && v1[t]<=b)
          {
           if(b%v1[t]==0)
              v[++q]=v1[t];
           t++;
          }
     s=0;
     for(i=1;i<(1<<q);i++)//i<nr de intersectii
        {
         nr=0;//nr=numarul de multimi Ai intersectate
         prod=1;
         for(j=0;j<q;j++)
            {
             if(i&(1<<j))//daca i are bitul j ==1
                {
                 nr++;
                 prod*=v[j+1];
                }
            }
         if(nr%2==0)
            s-=(a/prod);
         else
            s+=(a/prod);
        }
     if(s>=0)
        printf("%d\n",a-s);
     else
        printf("%d\n",a-(s*-1));
    }
return 0;
}