#include <cstdio>
        #include <cmath>
        using namespace std;
        bool prim[1000010], ok[1000010];
        int fp[100001], f[101], m;
        long long int solve(long long int x, long long int y)
        {
            long long int nrfact=0, k=0, sol=x, nr, prod, i, j;
            while(y>1)
            {
                k++;
                if(y%fp[k]==0)
                {
                    f[++nrfact]=fp[k];
                    while(y%fp[k]==0) y/=fp[k];
                }
                if(fp[k]>sqrt(y) && y>1)
                {
                    f[++nrfact]=y; y=0;
                }
            }
            for(i=1; i<(1<<nrfact);i++)
            {
                nr=0; prod=1;
                for(j=0; j<nrfact; j++)
                if(i&(1<<j))
                {
                    prod*=f[j+1]; nr++;
                }
                if(nr&1) nr=-1;
                else nr=1;
                sol=sol+nr*x/prod;
            }
            return sol;
        }
        void ciur (int n)
        {
            int i, j;
            for (i=1; ((i*i)<<1)+(i<<1)<=n; i++)
            {
                if (ok[i]==false)
                {
                    for (j=((i*i)<<1)+(i<<1); (j<<1)+1<=n; j+=(i<<1)+1) ok[j]=true;
                }
            }
            for (i=1; (i<<1)+1<=n; i++)
            {
                if (ok[i]==false)
                {
                    prim[(i<<1)+1]=true;
                    fp[++m]=(i<<1)+1;
                }
            }
        }
        int main()
        {
            int t, i;
            long long int x, y;
            freopen("pinex.in","r",stdin);
            freopen("pinex.out","w",stdout);
            scanf("%d",&t);
            ciur(1000000);
            for (i=1; i<=t; i++)
            {
                scanf("%lld%lld",&x,&y);
                printf("%d\n",solve(x,y));
            }
            fclose(stdin);
            fclose(stdout);
            return 0;
        }