#include <cstdio>
#include <math.h>

#define VMAX 1000007
#define NMAX 100007
#define LL long long

using namespace std;
int n, prim[NMAX], p = 1;
LL a, b, tmp, t, arr[NMAX], pos;
char ciur[VMAX], exc[NMAX];

void init()
{
    for(int i = 2; i<= VMAX-1; ++i)
    {
        if(ciur[i]) continue;
        if(i*i >= VMAX) break;
        for(int j = i*i; j<= VMAX-1; j+=i) ciur[j] = 1;
    }
    for(int i = 2; i<= VMAX-1; ++i)
    {
        if(ciur[i]) continue;
        prim[p] = i;
        p++;
    }
    --p;
}
void check()
{
    LL ct = 0, fact = 1;
    for(int i = 1; i< pos; ++i)
    {
        if(exc[i]-1) continue;
        ++ct;
        fact *= arr[i];
    }
    if(!ct) return ;
    if((ct&1) == 0) t -= a/fact;
    else t += a/fact;
}
void gen(int nr)
{
    if(nr == pos)
    {
        check();
        return ;
    }
    for(int i = 0; i<= 1; ++i)
    {
        exc[nr] = i;
        gen(nr+1);
    }
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    init();
    scanf("%d", &n);
    for(; n; --n)
    {
        pos = 1;
        scanf("%lld %lld", &a, &b);
        if(b == 1) {printf("%lld\n", a); continue;}
        for(int i = 1; i<= p; ++i)
        {
            if(b%prim[i]) continue;
            arr[pos] = prim[i];
            ++pos;
            while(b%prim[i] == 0) b/=prim[i];
        }
        if(b-1)
        {
            arr[pos] = b;
            ++pos;
        }
        t = 0;
        for(int i = 1; i< pos; ++i) exc[i] = 0;
        gen(1);
        printf("%lld\n", a-t);
    }
    return 0;
}