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

const int PMAX = 1e6 + 3;

vector <int> prime, primi;
bitset <PMAX> P;

void ciur () {

    int i, j;
    prime.push_back (2);
    for (i = 3; i < PMAX; i += 2) {
        if (!P[i])
            prime.push_back (i);
        for (j = 3 * i; j < PMAX; j += 2 * i)
            P[j] = 1;
    }

}

int d1 (int a) {

    int s = 0;
    while (a) {
        ++s;
        a &= a - 1;
    }
    return s;

}

void solve (const int &a, int b) {

    vector <int> :: iterator i = prime.begin ();
    int ans = 0, p;
    for (primi.clear (); *i **i <= b; ++i)
        if (b % *i == 0) {
            primi.push_back (*i);
            while (b % *i == 0)
                b /= *i;
        }
    if (b != 1)
        primi.push_back (b);
    int lim = 1 << primi.size (), k, j;
    for (k = 1; k < lim; ++k) {
        p = 1;
        for (j = 0; k >> j; ++j)
            if ((k >> j) & 1)
                p *= primi[j];
        if (d1 (k) & 1)
            ans += a / p;
        else
            ans -= a / p;
    }
    printf ("%d\n", a - ans);

}

int main () {

    freopen ("pinex.in", "r", stdin);
    freopen ("pinex.out", "w", stdout);
    int M, A, B;
    scanf ("%d", &M);
    ciur ();
    while (M--) {
        scanf ("%d%d", &A, &B);
        solve (A, B);
    }

}