#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "pinex.in" );
ofstream g ( "pinex.out" );
bool pr[1000001];

int prim[78500], nrp = 1;
long long fact[31];
int nrf;
void ciur ( int n )
{
    pr[0] = 1;
    pr[1] = 1;

    for ( int i = 4; i <= n; i += 2 )
        pr[i] = 1;

    for ( int i = 3; i * i <= n; i += 2 )
        if ( pr[i] == 0 )
            for ( int j = i * i; j <= n; j += i )
                pr[j] = 1;

    prim[1] = 2;

    for ( int i = 3; i <= n; i += 2 )
        if ( pr[i] == 0 ) prim[++nrp] = i;
}

void descf ( long long B )
{
    nrf = 0;

    for ( int i = 1; i <= nrp && 1LL * prim[i]*prim[i] <= B; i++ )
        if ( B % prim[i] == 0 )
        {
            fact[++nrf] = prim[i];

            do
            {
                B /= prim[i];
            }
            while ( B % prim[i] == 0 );
        }

    if ( B > 1 )
        fact[++nrf] = B;
}
int main()
{
    int m;
    long long A, B;
    ciur ( 1000000 );
    f >> m;

    for ( int i = 1; i <= m; i++ )
    {
        f >> A >> B;
        descf ( B );
        int nt = 1 << nrf;
        long long int card = A;

        for ( int j = 1; j < nt; j++ )
        {
            long long int prod = 1;
            int p2, nrdiv = 0;

            for ( int k = 0; ( p2 = 1 << k ) <= j; k++ )
                if ( ( p2 & j ) != 0 )
                {
                    prod *= fact[k + 1];
                    nrdiv++;
                }

            long long int t = A / prod;

            if ( nrdiv % 2 == 0 )
                card += t;
            else
                card -= t;
        }

        g << card << '\n';
    }

    return 0;
}