#include <cstdio>

using namespace std;

long long fact[100];
bool ciur[1000005];
int prim[1000005];
int nrfact,len;

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)
{
    int k=0,i;
    nrfact=0;
    for(i=1;i<=len && 1LL*prim[i]*prim[i]<=x && x>1;++i)
    {
        k=0;
        while(x%prim[i]==0)
        {
            x/=prim[i]; ++k;
        }
        if(k) fact[++nrfact]=prim[i];
    }
    if(x>1) fact[++nrfact]=x;
}

inline int Cnt(int x)
{
    int sol=0;
    for(;x;x=(x&(x-1)),++sol);
    return sol;
}

int main()
{
    long long A,B,sol;
    int i,stare,nr,Q;
    freopen ("pinex.in","r",stdin);
    freopen ("pinex.out","w",stdout);
    Ciur();
    scanf("%d", &Q);
    while(Q--)
    {
        scanf("%lld%lld", &A,&B);
        Descomp(B); sol=0;
        for(stare=1;stare<(1<<nrfact);++stare)
        {
            nr=0;
            long long prod=1;
            for(i=0;i<nrfact;++i)
                if((stare&(1<<i)))
                {
                    prod*=fact[i+1];
                    ++nr;
                }
            if(nr&1) sol+=A/prod;
            else sol-=A/prod;
        }
        printf("%lld\n", A-sol);
    }
    return 0;
}