#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

ifstream F("pinex.in");
ofstream G("pinex.out");

const int Bmax = 500010;
const int Fmax = 200010;

bool is_comp[Bmax+10];
int primes[Fmax],pnbr;

void get_primes()
{
    primes[0] = 2;
    for (int i=1;i<Bmax;++i)
        if ( is_comp[i] == 0 )
        {
            primes[++pnbr] = 2*i+1;
            for (int j=4*i+2;j<Bmax && j>0;j+=2*i+1)
                is_comp[j] = 1;
        }
}

int querys,fact[15],nfact;
long long A,B;

void get_fact()
{
    double up = sqrt(B);
    int now = 0;

    if ( B % primes[now] == 0 )
    {
        fact[++nfact] = primes[now];
        while ( B % primes[now] == 0 )
            B /= primes[now];
    }
    ++now;

    while ( B > 1 )
    {
        if ( B % primes[now] == 0 )
        {
            fact[++nfact] = primes[now];
            while ( B % primes[now] == 0 )
                B /= primes[now];
        }
        if ( primes[now] > up && B > 1 )
        {
            fact[++nfact] = B;
            B = 1;
        }
        now += 2;
    }
}

long long count()
{
    long long out=0;
    for (int i=1;i<(1<<nfact);++i)
    {
        int all = 1 , even = 1;
        for (int j=1,k=1;k<=i;++j,k<<=1)
            if ( k & i )
                all *= fact[j] , even ^= 1;
        if ( even == 0 )
            even = +1;
        else
            even = -1;
        out += even * ( A / all );
    }
    return out;
}

int main()
{
    get_primes();
    for (F>>querys;querys;querys--)
    {
        F>>A>>B;
        get_fact();
        G<<A-count()<<'\n';
        nfact = 0;
    }
}