#include <cstdio>

using namespace std;

int a,b,i,n,p,j,x[1000069],sol[1000069],ss,m,jj,y,d;
bool ok;

void afis(int k)
{
    int i,r=1;
    for (i=1; i<=k; i++) r*=x[sol[i]];
    if (k%2==0) ss-=a/r;
    else ss+=a/r;

}

void back(int k)
{
    int i;
    if (k<=m)
        for (i=sol[k-1]+1; i<=m; i++)
        {
            sol[k]=i;
            afis(k);
            back(k+1);
        }
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d", &n);
    for (i=1; i<=n; i++)
    {
        scanf("%d %d", &a, &b);

        ss=0;
        m=0;
        y=b; d=2;
        while (y>1)
          {
              p=0;
              while (y%d==0)
                {
                    p++;
                    y=y/d;
                }
              if (p>0) x[++m]=d;
              d++;
          }



        back(1);
        printf("%d\n", a-ss);

    }
        return 0;
    }