#include <fstream>
using namespace std;
int Q, a, b, i, j, dim, P[300001], divi[20], d, ok, aux, pr, nr, sol;
bool p[1000001];
bool sub[21];
int main()
{
    ifstream fin ("pinex.in");
    ofstream fout ("pinex.out");
    fin>>Q;
    p[1]=1;
    for (i=2; i<=500000; i++)
        if (p[i]==0)
            for (j=2*i; j<=1000000; j+=i)
                p[j]=1;
    for (i=1; i<=1000000; i++)
        if (p[i]==0)
            P[++dim]=i;
    for (int q=1; q<=Q; q++)
    {
        fin>>a>>b;
        dim=0;
        sol=0;
        for (d=1; P[d]<=b; d++)
            if (b%P[d]==0)
            {
                divi[++dim]=P[d];
                ok=1;
            }
        if (ok==0)
            divi[++dim]=b;
        for (j=1; j<=dim; j++)
        sub[j]=0;
        for (i=1; i<=(1<<dim)-1; i++)
        {
            pr=1;
            nr=0;
            aux=dim;
            while (sub[aux]==1)
            {
                sub[aux]=0;
                aux--;
            }
            sub[aux]=1;
            for (j=1; j<=dim; j++)
                if (sub[j]==1)
                {
                    pr*=divi[j];
                    nr++;
                }
            if (nr%2==0)
                sol-=a/pr;
            else
                sol+=a/pr;
        }
        fout<<a-sol<<"\n";
    }
}