#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "pinex.in" );
ofstream g ( "pinex.out" );
long long A, B;
long long fact[20];
int v[20];
long long nrprimi;
int lfact, semn = -1;
void afis ( int k )
{
    long long p = 1;

    for ( int i = 1; i <= k; i++ )
        p *= fact[v[i]];

    nrprimi = nrprimi + semn * A / p;
}
bool valid ( int x )
{
    if ( v[x - 1] >= v[x] )
        return 0;

    return 1;
}
void backt ( int x, int k )
{
    if ( x <= k )
        for ( int i = v[x - 1] + 1; i <= lfact - k + x; i++ )
        {
            v[x] = i;
            backt ( x + 1, k );
        }
    else
        afis ( k );
}
int main()
{
    int M;
    f >> M;

    for ( int i = 1; i <= M; i++ )
    {
        f >> A >> B;
        lfact = 0;
        semn = -1;

        if ( B % 2 == 0 )
        {
            fact[++lfact] = 2;

            while ( B % 2 == 0 )
                B /= 2;
        }

        for ( long long j = 3; j * j <= B; j += 2 )
            if ( B % j == 0 )
            {
                fact[++lfact] = j;

                while ( B % j == 0 )
                    B /= j;
            }

        if ( B > 1 )
            fact[++lfact] = B;

        nrprimi = A;

        for ( int j = 1; j <= lfact; j++ )
        {
            backt ( 1, j );
            semn = -semn;
        }

        g << nrprimi << '\n';
    }

    return 0;
}