#include<fstream>
#include<bitset>
#include<vector>
#define CIURMAX 1000010
#define LIM 1000
#define LIM2 1000000
#define NMAX 25

using namespace std;

//bitset<CIURMAX> ciur;
vector<int> prime;
int n, nr;
long long A, B, d[NMAX];
bool ciur[CIURMAX];

ifstream f("pinex.in");
ofstream g("pinex.out");

void Ciur()
{
    int i;
    long long j, x;

    for (i=2; i<=LIM; ++i)
        if (!ciur[i])
        {
            x=i;
            prime.push_back(i);
            for (j=x*x; j<=LIM2; j*=x)
                ciur[j]=1;
        }
    for(i=LIM; i<=LIM2; ++i)
        if (!ciur[i]) prime.push_back(i);
}

long long calculeaza(long long A)
{
    int lim=1<<nr+1, conf, auxconf, ap, p, i;
    long long sol=0;

    for (conf=1; conf<lim; ++conf)
    {
        auxconf=conf;
        p=1; ap=0;
        for (i=0; i<=nr; ++i)
            if ((auxconf&(1<<i))!=0)
            {
                ++ap;
                p*=d[i];
            }
        if (ap%2==1) sol+=A/p;
        else sol-=A/p;
    }
    return sol;
}

void Solve()
{
    int i;

    f>>n;
    while (n--)
    {
        f>>A>>B;

        nr=0; i=0;
        while (prime[i]*prime[i]<=B)
        {
            if (B%prime[i]==0)
            {
                d[nr++]=prime[i];
                while (B%prime[i]==0) B/=prime[i];
            }
            ++i;
        }
        if (B!=1) d[nr++]=B;

        --nr;
        g<<A-calculeaza(A)<<"\n";
    }
}

int main()
{
    Ciur();

    Solve();

    f.close();
    g.close();
    return 0;
}