#include<cstdio>
int v[10001];
int main()
{
 int m,f,a,b,d,cb,p,q,i,j,prod,k,s,nr;
 freopen("pinex.in","r",stdin);
 freopen("pinex.out","w",stdout);
 scanf("%d",&m);
 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++;
          }
     s=0;
     for(i=1;i<(1<<q);i++)
        {
         nr=0;
         prod=1;
         for(j=0;j<q;j++)
            {
             if(i&(1<<j))
                {
                 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;
}