#include <cstdio>
#define N 1000010
using namespace std;
long long a,b,sol,F[100],y[1<<16];
int t,np,k,P[N];
void ciur(),factorizare();
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    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;
            for(j=i*i;j<=1000000;j+=2*i)
                P[j]=1;
        }
    for(;i<=1000000;i++)
    if(!P[i])
    {
        P[++np]=i;
    }
}
void factorizare()
{
    int i,e,u;
    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];
    printf("%lld\n",sol);
}