#include <fstream>
#include <vector>
#include <cmath>
#define amax 1000005
using namespace std;
vector <long long> Dp;
long long st[amax],fprimi[amax];bool prim[amax];
long long dim,ndiv,fp;
void precalcul()
{
    long long d,i;
    for (d=2;d<amax;d++)
    {
        if (!prim[d])
        {
            fprimi[++fp]=d;
            for (i=2*d;i<amax;i+=d)
                prim[i]=1;
        }
    }
}
void desc(long long x)
{
    long long d,y;
    Dp.clear();
    for (d=1; d<=fp && x!=1 ;d++)
    {
        y=fprimi[d];
        if (x%y==0)
        {
            Dp.push_back(y);
            while (x%y==0) x/=y;
        }
    }
    dim=Dp.size();
}
void divizori(long long x)
{
    long long i,p=1,prod=1;
    st[p]=0;
    while (p>0)
    {
        if (st[p]<dim)
        {
            st[p]++;
            {
                for (i=1,prod=1;i<=p;i++)
                    prod*=(Dp[st[i]-1]);
                if (p%2) ndiv+=(x/prod);
                else ndiv-=(x/prod);
            }
            if (p<dim)
                st[++p]=st[p-1];
        }
        else p--;
    }
}
int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    precalcul();
    long long a,b,i,t;
    fin>>t;
    for (i=1;i<=t;i++)
    {
        fin>>a>>b;
        desc(b);
        ndiv=0;divizori(a);
        fout<<a-ndiv<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}