using namespace std;
#include <fstream>
ifstream fin("pinex.in");
ofstream fout("pinex.out");

const long long Vmax = 1000000 * 1000000;
const int rad = 1000000;
const int Pmax = 80000; // sunt exact 78499 numere prime pana in 1000000

bool isPrime[rad+5];
int prim[Pmax], nrP = 1;
int v[30], nrfact;
long long nr, a, b, termen;

void ciur() ;
void rezolva() ;

int main()
{
    int m;
    ciur();
    fin>>m;
    for(; m; --m)
    {
        fin>>a>>b; nr = 0; nrfact = 0, termen = 1;
        rezolva();
        fout<<a-nr<<'\n';
    }
    return 0;
}


void ciur()
{
    int i, j;
    for(i=2; i<=rad; ++i) isPrime[i] = i%2;
    prim[0] = 2;
    for(i=3; i<=rad; ++i)
    {
        while(!isPrime[i]) ++i;
        prim[nrP++] = i;
        for(j=i+i+i; j<=rad; j += i+i) isPrime[j] = 0;
    }
}


void rezolva()
{
    int i, j, t;
    for(i=0; b!=1; ++i)
        if(b % prim[i] == 0)
        {v[nrfact++] = i; while(b % prim[i] == 0) b /= prim[i];}
    for(i=1; i < (1<<nrfact); ++i)
    {
        termen = 1; t = 0;
        for(j=0; j<nrfact; ++j)
            if(i&(1<<j))
                {termen *= prim[v[j]]; ++t;}
        termen = a/termen;
        if(t%2==0) nr -= termen;
        else nr += termen;
    }
}