#include <fstream>

using namespace std;
ifstream in ("pinex.in");
ofstream out ("pinex.out");
bool v[1000006];
long long p[50];
void quang (long long &s, long long a, long long n)
{
    int ca=a,cnt=0,pt=1,k=1;
    while(ca)
    {
        if(ca%2==1)
            cnt++;
        ca>>=1;
    }
    while(a)
    {
        if(a%2==1)
        {
            pt=pt*1LL*p[k];
        }
        k++;
        a>>=1;
    }
    if(cnt%2==0)
        s+=n/pt;
    else
        s-=n/pt;
}
int main()
{
    long long m,a,b,i,j,y,x,s=0;
    in>>m;
    v[0]=v[1]=1;
    for(i=2;i*i<=1000000;i++)
        if(v[i]==0)
            for(j=i*i;j<=1000000;j+=i)
                v[j]=1;
    for(y=1;y<=m;y++)
    {
        in>>a>>b;
        j=0;
        s=0;
        for(i=2;i*i<=b;i++)
        {
            if(v[i]==0 && b%i==0)
            {
                p[++j]=i;
                while(b%i==0)
                    b/=i;
            }
        }
        if(b)
            p[++j]=b;
        x=1<<j;
        for(i=0;i<x;i++)
        {
            quang(s,i,a);
        }
        out<<s<<'\n';
    }
    return 0;
}