#include <cstdio>

#define Vmax 1000010

using namespace std;

int m , A , B;
int pm[Vmax] , div[100];

bool ok[Vmax];

void ciur()
{
    for (int i = 2; i * i <= Vmax; ++i)
     for (int j = i * 2; j <= Vmax && !ok[i]; j += i)
      ok[j] = true;

    for (int i = 2; i <= Vmax; ++i)
     if (!ok[i]) pm[++pm[0]] = i;
}

void make_div(int n)
{
    div[0] = 0;

    for (int i = 1; B > 1; ++i)
     if (B % pm[i] == 0)
    {
        div[++div[0]] = pm[i];

        while (B % pm[i] == 0) B /= pm[i];
    }
}

int solve()
{
    make_div(B); int sol = 0;

    for (int x = 1; x < (1 << div[0]); ++x)
    {
        int cnt = 0 , multiplu = 1;

        for (int i = 0; i < div[0]; ++i)
         if (x >> i & 1) multiplu *= div[i+1] , cnt++;

        sol += (cnt & 1) ? A / multiplu : (-1) * A / multiplu;
    }

    return A - sol;
}


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

    scanf("%d", &m);

    ciur();

    for ( ; m ; --m)
    {
        scanf("%d %d", &A, &B);

        printf("%d\n", solve());
    }


    return 0;
}