#include <cstdio>

#define FIN     "pinex.in"
#define FOU     "pinex.out"
#define lint    long long
#define BMAX    1000000
#define MAX     (1 << 17)

lint A, B, put[30];
int T, P[BMAX - 920000];
unsigned char V[MAX];

int square( lint N )
{
    lint i, cnt;
    for ( i = 1, cnt = ( 1 << 20 ) ; cnt ; cnt >>= 1)
        if ( (lint) (i + cnt) * (i + cnt) <= N) i += cnt;

    return i;
}
void prec()
{
    P[++P[0]] = 2;

    for (int i = 3; i < BMAX; i += 2)
    {
        if (V[i >> 4] & (1 << ((i >> 1) & 7))) continue;

        P[++P[0]] = i;

        for (int j = i + (i << 1); j < BMAX; j += i << 1)
            V[j >> 4] |= 1 << ((j >> 1) & 7);
    }
}

int fact(lint N)
{
    int k = 0, j = square( N );

    for (int i = 1; P[i] <= j ; i++)
        if (N % P[i] == 0)
        {
            put[++k] = P[i];
            while (N % P[i] == 0)
                N /= P[i];
        }
    if (N > 1)
        put[++k] = N;

    return k;
}

void solve(lint A, lint B)
{
    int k = fact(B);

    lint sol = A;

    for (int i = 1; i < (1 << k); i++)
    {
        lint nr_mul = 0, elem = 1;
        for (int j = 0; j < k; j++)
            if ( i & (1 << j) )
                elem *= (lint) put[j + 1], nr_mul++;

        if ( nr_mul & 1 ) nr_mul = -1;
        else nr_mul = 1;

        sol += (lint) nr_mul * A / elem;
    }

    printf ("%lld\n", sol);
}

int main()
{

    freopen(FIN, "r", stdin);
    freopen(FOU, "w", stdout);

    prec();

    for (scanf("%d", &T); T ; --T)
    {
        scanf("%lld %lld", &A, &B);
        solve(A , B);
    }

    return 0;
}