#include <bits/stdc++.h>
#define maxp 1000000
using namespace std;

long long a,b;
bool c[maxp];
int diviz[maxp],k,fprim[80005];

void ciur()
{
    for (int i=2;i<=maxp;++i)
    {
        if (!c[i])
            {
                for (int j=i+i;j<=maxp;j+=i)
                c[j]=1;
                diviz[++k]=i;
            }
    }
}
void solve()
{
    fprim[0]=0;
    long long total=a;
    for (int i=1;i<=k && diviz[i]*diviz[i]<=b;++i)
    {
        if (b%diviz[i]==0)
            {
                fprim[++fprim[0]]=diviz[i];
                while (b%diviz[i]==0)
                    b/=diviz[i];
            }
    }
    if (b>1)
        fprim[++fprim[0]]=b;
    for (int i=1;i<(1<<fprim[0]);++i)///asa iau toate posibilitatile de divizori
    {
        int nr=0;
        long long t=1;
        for (int j=0;j<fprim[0];++j)
            if (i & (1<<j)) ///daca e in componenta binara a lui i
        {
            ++nr;
            t*=fprim[j+1];
        }
        if (nr%2==1)
            total-=a/t;
        else
            total+=a/t;
    }
    printf("%lld\n",total);
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int n;
    scanf("%d",&n);
    ciur();
    for (int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&a,&b);
        solve();
    }
    return 0;
}