#include <cstdio>
#define BIT(x) (1<<(x))
#define CMAX 1000010
#define CNMAX 100010

using namespace std;
typedef long long llong;

char ciur[CMAX / 8 + 3];
int np[CNMAX], lnp;
int fact[12], lfact;
llong a, b;

inline bool eprim(int i)
{
    return (ciur[i >> 3] & BIT(i & 7)) != 0;
}

void genCiur()
{
    int i, j;
    lnp = 1;
    np[0] = 2;
    for(i = 4; i < CMAX; i += 2)
        ciur[i >> 3] |= BIT(i & 7);
    for(i = 3; i < CMAX; i += 2)
    {
        if((ciur[i >> 3] & BIT(i & 7)) == 0)
        {
            np[lnp++] = i;
            for(j = i + i; j < CMAX; j += i)
                ciur[j >> 3] |= BIT(j & 7);
        }
    }
}

void getFact(llong a)
{
    int i;
    lfact = 0;
    for(i = 0; i < lnp && a != 1; i++)
    {
        if(a % np[i] == 0)
        {
            fact[lfact++] = np[i];
            while(a % np[i] == 0)
                a /= np[i];
        }
    }
    if(a != 1) fact[lfact++] = a;
}

int main()
{
    llong res, sub;
    int ncom, i, j, nbiti;
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    genCiur();
    scanf("%d", &ncom);
    while(ncom--)
    {
        scanf("%lld%lld", &a, &b);
        getFact(b);
        res = 0;
        for(i = 1; i < BIT(lfact); i++)
        {
            sub = 1;
            nbiti = 0;
            for(j = 0; j < lfact; j++)
            {
                if(i & BIT(j))
                {
                    nbiti++;
                    sub *= fact[j];
                }
            }
            if(nbiti & 1) res += a / sub;
            else res -= a / sub;
        }
        res = a - res;
        printf("%lld\n", res);
    }
    return 0;
}