#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;

#define pb push_back
#define DIM 1000005

vector <int> prim,fact;
long long a,b,nrt;
bitset <DIM> viz;
int t,m;

void init ()
{
    int i,j;

    for (i=2; i<DIM; ++i)
        if (!viz[i])
        {
            prim.pb (i);
            for (j=i+i; j<DIM; j+=i)
                viz[j]=1;
        }
}

void solve ()
{
    int d,i,j,semn;
    long long p;

    nrt=m=0;
    fact.clear ();
    for (d=0; prim[d]*prim[d]<=b && d<(int)prim.size (); ++d)
        if (b%prim[d]==0)
            for (++m, fact.pb (prim[d]); b%prim[d]==0; b/=prim[d]);
    if (b>1)
    {
        ++m;
        fact.pb (b);
    }
    for (i=1; i<(1<<m); ++i)
    {
        semn=p=1;
        for (j=0; j<m; ++j)
            if (i&(1<<j))
            {
                semn^=1;
                p*=fact[j];
            }
        if (semn)
            nrt-=a/p;
        else
            nrt+=a/p;
    }
    printf ("%lld\n",a-nrt);
}

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

    init ();
    scanf ("%d",&t);
    for (i=1; i<=t; ++i)
    {
        scanf ("%lld%lld",&a,&b);
        solve ();
    }
}