#include <cstdio>
#include <bitset>

#define XMax 4000000
#define LL long long
#define PMax 1000000

using namespace std;

LL A, B, S;
bitset <XMax> V;
int Primes[PMax], F[XMax];

void Eratosthenes ()
{
    for (int i=2; i*i<XMax; ++i)
    {
        if (!V[i])
        {
            Primes[++Primes[0]]=i;
            for (int j=i*i; 1LL*j*j<=B; j+=i)
            {
                V[j]=1;
            }
        }
    }
}

void Decompose ()
{
    F[0]=0;
    for (int i=1; 1LL*Primes[i]*Primes[i]<=B and i<=Primes[0] and B>1; ++i)
    {
        if (B%Primes[i]==0)
        {
            F[++F[0]]=Primes[i];
        }
        for (; B%Primes[i]==0; B/=Primes[i]);
    }
    if (B>1)
    {
        F[++F[0]]=B;
    }
}

void Pinex ()
{
    S=0;
    for (int Conf=1; Conf<(1<<F[0]); ++Conf)
    {
        int Sign=-1; LL X=1;
        for (int i=0; i<F[0]; ++i)
        {
            if (Conf&(1<<i))
            {
                Sign=-Sign;
                X*=F[i+1];
            }
        }
        S+=(Sign*(A/X));
    }
    S=A-S;
}

int main()
{
    freopen ("pinex.in", "r", stdin);
    freopen ("pinex.out", "w", stdout);
    Eratosthenes ();
    int T;
    scanf ("%d", &T);
    for (; T>0; --T)
    {
        scanf ("%lld %lld", &A, &B);
        Decompose ();
        Pinex ();
        printf ("%lld\n", S);
    }
    return 0;
}