#include <cstdio>
#define N 1000010
using namespace std;
long long a,b,sol,P[N],F[100];
int t,np,k;
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();
        back(1,0,1);
        printf("%lld\n",sol);
    }
    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;
    scanf("%lld%lld",&a,&b);k=0;sol=0;
    for(i=1;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;
}
void back(long long d,int c,int p)
{
    if(p==k+1)
    {
        if(c%2)sol-=a/d;
        else sol+=a/d;
        return;
    }
    back(d,c,p+1);
    back(d*F[p],c+1,p+1);
}