#include <cstdio>
#define VMax 1000000
#define NMax 4096
#define FMax 14
#define llt long long

struct comb{ llt lcm,f; } e[2][NMax+1];

char ciur[VMax+1];
llt prime[VMax/10];
llt v[FMax+1];

void Precalc()
{
    int i,j,t=0;

    prime[ ++prime[0] ] = 2;
    for(i = 2; i <= VMax; i+=2) ciur[i] = 1;
    for(i = 3; i <= VMax; i+=2)
    if( !ciur[i] )
    {
        prime[ ++prime[0] ] = i;
        for(j = 3*i; j <= VMax; j+=2*i) ciur[j] = 1;
    }
    prime[ ++prime[0] ] = 1000000007;
}

int main(){
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    int i,j,T,s,l,x,y,r,a,sgn;
    llt A,B,ans;

    Precalc();
    scanf("%d",&T);

    while(T--)
    {
        scanf("%lld %lld",&A,&B);

        ans = v[0] = 0;
        for(i = 1; prime[i]*prime[i] <= B; ++i)
        if( B % prime[i] == 0 )
        {
            v[ ++v[0] ] = prime[i];
            while( B % prime[i] == 0 ) B /= prime[i];
        }
        if( B > 1 ) v[ ++v[0] ] = B;

        e[0][0].f = 1;
        e[0][1].f = 0;
        e[0][1].lcm = 1;

        for(sgn = l = i = 1; i <= v[0]; ++i, l = 1-l, sgn *= -1)
        {

            e[l][0].f = 0;
            for(j = 1; j <= e[1-l][0].f; ++j)
                for(s = e[1-l][j].f+1; s <= v[0]; ++s)
                {
                    e[l][ ++e[l][0].f ].f = s;

                    x = a = e[1-l][j].lcm;
                    y = v[s];
                    while(y) { r = x%y; x=y; y=r; }

                    e[l][ e[l][0].f ].lcm = a*v[s]/x;
                }

            for(j = 1; j <= e[l][0].f; ++j) ans = ans + sgn * ( A/e[l][j].lcm );
        }

        printf("%lld\n",A-ans);
    }



return 0;
}