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

bool viz[DIM];
long long int Primes[100000], nr, A[50];
long long int a, b;

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

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

void Solve()
{
    long long 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 && 1LL * 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 %lld", &a, &b);
        Solve();
    }
}