// Principiul includerii si excluderii
#include <cstdio>
#define DIM 1 << 20
using namespace std;
FILE *fin=freopen("pinex.in","r",stdin);
FILE *fout=freopen("pinex.out","w",stdout);

bool viz[DIM];
int Primes[1 << 17], nr, A[20];
int b;
long long int a;

void Compute()
{
    int i, j;
    Primes[++nr] = 2;

    for(i = 3; i * i < DIM; i += 2)
        if( !viz[i] )
        {
            Primes[++nr] = i;
            for(j = i * i; j < DIM; j += 2 * i)
                viz[j] = 1;
        }
}

void Solve()
{
    int d = 1, t = 0, i, j, semn;
    long long cnt = a, nr, P;

    while( b > 1 )
    {
        if( b % Primes[d] == 0 )
        {
            A[++t] = Primes[d];
            while( b % Primes[d] == 0 )
                b /= Primes[d];
        }

        if( b > 1 && Primes[d] * Primes[d] > b )
        {
            A[++t] = b, b = 1;
        }

        ++d;
    }


    for(i = 1; i < (1 << t); ++i)
    {
        nr = 0, P = 1;
        for(j = 0; j < t; ++j)
            if( i & (1 << j) )
            {
                ++nr;
                P = 1LL * P * A[j + 1];
            }
        if( nr % 2 == 0 )
            semn = 1;
        else
            semn = -1;

        cnt += 1LL * semn * a / P;
    }

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

int main()
{
    Compute();
    int m;

    for(scanf("%d", &m); m > 0 ; --m)
    {
        scanf("%lld %d", &a, &b);
        Solve();
    }
}