#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
vector <long long> Dp;
vector <long long> st;
long long dim,ndiv;
void desc(long long x)
{
    long long d;
    Dp.clear();
    for (d=2; d<=x && d!=1 ;d++)
    {
        if (x%d==0)
        {
            Dp.push_back(d);
            while (x%d==0) x/=d;
        }
    }
    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");
    long long a,b,i,t;
    fin>>t;
    for (i=1;i<=t;i++)
    {
        fin>>a>>b;
        desc(b);
        st.resize(dim+1);
        ndiv=0;divizori(a);
        fout<<a-ndiv<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}