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

#define MAX 1000005
#define DIM 500005
#define MOD 9973

int prime[DIM],fact[DIM];
bitset <MAX> viz;
long long nrt;
int t,n,m;

void init ()
{
    int i,j;

    prime[++n]=2;
    for (i=3; i<MAX; i+=2)
        if (!viz[i>>1])
        {
            prime[++n]=i;
            for (j=3*i; j<MAX; j+=(i<<1))
                viz[j>>1]=1;
        }
}

void solve ()
{
    long long a,b,val;
    int stare,i,semn;

    m=0;
    scanf ("%lld%lld",&a,&b);
    for (i=1; i<=n && 1LL*prime[i]*prime[i]<=b; ++i)
        if (!(b%prime[i]))
            for (fact[++m]=prime[i]; !(b%prime[i]); b/=prime[i]);
    if (b>1)
        fact[++m]=b;

    nrt=a;
    for (stare=1; stare<(1<<m); ++stare)
    {
        semn=val=1;
        for (i=1; i<=m; ++i)
            if (stare&(1<<(i-1)))
            {
                semn^=1;
                val*=fact[i];
            }
        if (semn)
            nrt+=a/val;
        else
            nrt-=a/val;
    }
    printf ("%lld\n",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)
        solve ();

    return 0;
}