#include <cstdio>
#include <cmath>
using namespace std;

typedef long long I64;

int M; I64 A,B;

const int Lim = 500000;
const int Nmax = 1010;

bool Prim[Lim+5];
int Prime[Lim+5],Fact[Nmax],NbrP,NbrF;

void Erathostenes()
{
    Prime[0]=2, NbrP=0;
    for (int i=1;i<=Lim;++i)
        if ( Prim[i] == 0 )
        {
            Prime[++NbrP]=2*i+1;
            for (int j=2*i*i+2*i;j<=Lim && j>0;j+=2*i+1)
                Prim[j]=1;
        }
}

void Factorizare()
{
    double UpperLim = sqrt( B );
    NbrF = 0;

    for ( int i=0; B > 1 ; ++i )
    {
        if ( B % Prime[i] == 0 )
        {
            Fact[++NbrF] = Prime[i];
            while ( B % Prime[i] == 0 ) B /= Prime[i];
        }
        if ( B>1 && Prime[i] > UpperLim )
        {
            Fact[++NbrF] = B;
            B = 1;
        }
    }
}

I64 Calc()
{
    int Stop = 1 << NbrF , Step = 1; I64 Prod , Sol=0;
    for (int i=1;i<Stop;++i)
    {
        Prod = 1 , Step = 0;
        for (int j=0;j<NbrF;++j)
            if ( i & ( 1<<j ) )
                Prod *= I64( Fact[NbrF-j] ), ++Step;
        Sol += ( Step & 1 ? 1 : -1 ) * ( A / Prod );
    }
    return Sol;
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    Erathostenes();

    for ( scanf("%d\n",&M) ; M>0 ; --M )
    {
        scanf("%lld %lld\n",&A,&B), Factorizare();
        printf("%lld\n",A-Calc());
    }

    fclose(stdin), fclose(stdout);
    return 0;
}