#include <cstdio>

using namespace std;

bool ciur[1000005];
int prim[100000],fact[1000];

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[++prim[0]]=2;
    for(i=3;i<1000000;i+=2)
        if(!ciur[i])
            prim[++prim[0]]=i;
}

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

inline long long Solve(long long A)
{
    long long sol=0,prod;
    int i,j,val,nr;
    val=(1<<fact[0]); sol=A;
    for(i=1;i<val;++i)
    {
        nr=0; prod=1;
        for(j=0;j<fact[0];++j)
            if((1<<j)&i)
            {
                ++nr;
                prod=prod*1LL*fact[j+1];
            }
        if(nr%2)
            nr=-1;
        else
            nr=1;
        sol+=1LL*nr*A/prod;
    }
    return sol;
}

int main()
{
    int T;
    long long A,B;
    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", Solve(A));
    }
    return 0;
}