#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(),back(long long,int,int);
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;
    back(1,1,1);
    printf("%lld\n",sol);
}
void back(long long val,int par,int pos)
{
    if(pos==k+1){sol+=par*a/val;return;}
    back(val,par,pos+1);
    for(int j=pos;j<=k;j++)
    {
        if(val*F[pos]>a)return;
        back(val*F[pos],-par,pos+1);
    }
}