#include<cstdio>
int v[10001],v1[1000001],q,e;
char ciur[1000001];
void desc(long long n)
{
 int i=1;
 q=0;
 while(i<=e && v1[i]*v1[i]<=n)
      {
       if(n%v1[i]==0)
          {
           v[++q]=v1[i];
           while(n%v1[i]==0)
                 n/=v1[i];
          }
       i++;
      }
 if(n!=1)
   v[++q]=n;
}
int main()
{
    long long prod,m,f,a,b,d,i,j,s,nr,t;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%lld",&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;
        }
    }
    for(i=2; i<=1000000; i++)
    {
        if(ciur[i]==0)
            v1[++e]=i;
    }
    for(f=1; f<=m; f++)
    {
        scanf("%lld%lld",&a,&b);
        q=0;
        t=1;
        /*q=0;
        for(i=1;i<=b && i<=e;i++)
           {
            if(ciur[i]==0 && b%i==0)
               v[++q]=i;
           }*/
        /*while(t<=e && v1[t]<=b)
        {
            if(b%v1[t]==0)
                v[++q]=v1[t];
            t++;
        }*/
        desc(b);
        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("%lld\n",a-s);
        else
            printf("%lld\n",a-(s*-1));
    }
    return 0;
}