#include <fstream>

#define Pdim 1000002
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long A,B,nrdiv,M;
long long D[30],Prime[80000],Ciur[Pdim];
void prep()
{
    for(int i=2;i<Pdim;i++)
    {
        if(!Ciur[i])
        {
            Prime[++Prime[0]] = i;
            for(int j=i+i;j<=Pdim;j+=i)
                Ciur[j] = 1;
        }
    }
}
void divizori_primi(long long nr)
{
    nrdiv = 0;
    for(long long i=1; Prime[i] * Prime[i] <= nr;i++)
    {
        if(nr % Prime[i] == 0)
        {
            D[++nrdiv] = Prime[i];
            while(nr % Prime[i] == 0)
                nr /= Prime[i];
        }
    }
    if(nr!=1)
        D[++nrdiv] = nr;
}
long long pinex(long long val)
{
    long long i,nr,j;
    long long prod,sol = A;
    for(i=1;i<=val;i++)
    {
        nr=0;prod = 1;
        for(j=0;j<nrdiv;j++)
        {
            if((1<<j)&i)
            {
                nr++;
                prod *= D[j+1];
            }
        }
        if(nr%2)
            nr = -1;
        else
            nr=1;
        sol = sol + nr * A/prod;
    }
    return sol;
}
int main()
{
    fin>>M;
    prep();
    while(M--)
    {
        fin>>A>>B;
        divizori_primi(B);
        fout<<pinex((1<<nrdiv)-1)<<'\n';
    }
    return 0;
}