#include <cstdio>

using namespace std;

int f[100005],prim[1000005],len;
bool ciur[1000005];
long long A,B;

inline void Ciur()
{
    int i,j;
    for(i=3;i<=1000;i+=2)
        if(!ciur[i])
            for(j=i*i;j<=1000000;j+=2*i) ciur[j]=true;
    prim[++len]=2;
    for(i=3;i<=1000000;i+=2)
        if(!ciur[i]) prim[++len]=i;
}

inline void Descomp(long long x)
{
    long long d=3;
    int i,k;
    f[0]=0;
    for(i=1;i<=len && 1LL*prim[i]*prim[i]<=x;++i)
    {
        k=0;
        while(x%prim[i]==0)
        {
            x/=prim[i]; ++k;
        }
        if(k) f[++f[0]]=prim[i];
    }
    if(x>1) f[++f[0]]=x;
}

inline long long Solve()
{
    long long sol=0,prod;
    int stare,i,cnt;
    for(stare=1;stare<(1<<f[0]);++stare)
    {
        for(i=cnt=0,prod=1;i<f[0];++i)
            if((1<<i)&stare)
            {
                prod*=f[i+1];
                ++cnt;
            }
        if(cnt%2) sol+=A/prod;
        else sol-=A/prod;
    }
    return sol;
}

int main()
{
    int T,i;
    freopen ("pinex.in","r",stdin);
    freopen ("pinex.out","w",stdout);
    Ciur();


    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld%lld", &A,&B);
        Descomp(B);
        printf("%lld\n", A-Solve());
    }
    return 0;
}