#include<fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int A, B, t, a[1000002], d[1000002], p[1000002], k, viz[1000002], nr, sol;
void back(int niv)
{
    if(niv>nr)
    {
        int ok=0;
        long long prim=1;
        for(int i=1;i<=nr;i++)
            if(a[i]!=0)
            {
                ok++;
                prim*=d[i];
            }
        if(ok%2==0)
            sol+=A/prim;
        else sol-=A/prim;
    }
    else
    {
        for(int i=0;i<2;i++)
        {
            a[niv]=i;
            back(niv+1);
        }
    }
}
void ciur()
{
    int i;
    for(i=2;i<=1000;i++)
    {
        if(viz[i]==0)
        {
            for(int j=i+i;j<=1000000;j+=i)
                    viz[i]=1;
            p[++k]=i;
        }
    }
    for(;i<=1000000;i++)
        if(viz[i]==0)
            p[++k]=i;
}
int main()
{
    f>>t;
    ciur();
    for(;t>0;t--)
    {
        f>>A>>B;
        nr=0;
        for(int i=1;i<=k && p[i]*p[i]<=B;i++)
            if(B%p[i]==0)
            {
                d[++nr]=p[i];
                while(B%p[i]==0)
                    B/=p[i];
            }
        if(B>1)
            d[++nr]=B;
        sol=0;
        back(1);
        /*long long n=(1LL<<nr)-1;
        for(int i=1;i<=n;i++)
        {
            int ok=0;
            long long p=1;
            for(int j=0;j<nr;j++)
                if( ((i>>j)&1LL) ==1LL)
                {
                    ok++;
                    p*=(d[j+1]*1LL);
                }
            if(ok%2==0)
                sol+=A/p;
            else
                sol-=A/p;
        }*/
        g<<sol<<"\n";
    }
    return 0;
}