#include <cstdio>
#include <fstream>
#define N 1000010
using namespace std;
long long a,b,sol,F[100],y[1<<16];
int t,np,k,st,P[N];
void ciur(),factorizare();
ifstream fin("pinex.in");
ofstream fout("pinex.out");

int main()
{
    //freopen("pinex.in","r",stdin);
    //freopen("pinex.out","w",stdout);
    ciur();
    fin>>t;//scanf("%d",&t);
    for(;t;t--)
        factorizare();
    return 0;
}
void ciur()
{
    int i,j;
    P[1]=2;np=1;
    for(i=3;i<=1000;i+=2)
        if(!P[i])
        {
            P[++np]=i;st=2*i;
            for(j=i*i;j<=1000000;j+=st)
                P[j]=1;
        }
    for(;i<=1000000;i+=2)
    if(!P[i])
    {
        P[++np]=i;
    }
}
void factorizare()
{
    int i,e,u;
    fin>>a>>b;//scanf("%lld%lld",&a,&b);
    k=0;sol=0;
    for(i=1;1LL*P[i]*P[i]<=b&&i<=np;i++)
        if(b%P[i]==0)
        {
            F[++k]=P[i];
            while(b%P[i]==0)b/=P[i];
        }
    if(b>1)F[++k]=b;
    y[1]=1;u=1;
    for(i=1;i<=k;i++,u*=2)
        for(e=1;e<=u;e++)
            y[e+u]=-y[e]*F[i];
    for(i=1;i<=u;i++)
        sol+=a/y[i];
    fout<<sol<<'\n';//printf("%lld\n",sol);
}