#include<fstream>
#include<vector>

using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");

int nr,k,i,t,ok[1000005];
long long j,sol,p,x,y;
vector<long long> a,b;

void ciur()
{
    i=3;
    a.push_back(2);
    while (i<=1000000)
    {
        if (!ok[i])
        {
            a.push_back(i);
            for (j=(long long)i*i;j<=1000000;j=j+(2*i))
                ok[j]=1;
        }
        i+=2;
    }
}

int main()
{
    in>>t;
    ciur();

    for (i=1;i<=t;i++)
    {
        in>>x>>y;
        sol=0;

        for (j=0;j<a.size();j++)
            if (y%a[j]==0)
            {
                b.push_back(a[j]);
                while (y%a[j]==0) y/=a[j];
                if (y==1) break;
            }
        if (y!=1) b.push_back(y);

        for (j=1;j<=(1<<b.size())-1;j++)
        {
            p=1;
            nr=0;
            for (k=0;k<b.size();k++)
                if (j & (1<<k))
                {
                    nr++;
                    p*=b[k];
                }
            if (nr%2) sol+=(x-x/p);
                else sol-=(x-x/p);
        }
        b.clear();
        out<<sol<<'\n';
    }
}