#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;
    }

}


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

    int d;
    vector <int> :: iterator i = prime.begin ();
    long long p, ans = 0;
    for (primi.clear (); *i * *i <= b && i != prime.end (); ++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;
        d = 0;
        for (j = 0; k >> j; ++j)
            if ((k >> j) & 1) {
                p *= 1LL * primi[j];
                ++d;
            }
        if (d & 1)
            ans += a / p;
        else
            ans -= a / p;
    }
    printf ("%lld\n", a - ans);

}

int main () {

    freopen ("pinex.in", "r", stdin);
    freopen ("pinex.out", "w", stdout);
    int M;
    long long A, B;
    scanf ("%d", &M);
    ciur ();
    for (vector <int> :: iterator i = prime.begin (); i != prime.end (); ++i) {
        if (*i == 0)
            printf ("bitch");
    }
    printf ("%d ", *prime.end ());
    while (M--) {
        scanf ("%lld%lld", &A, &B);
        solve (A, B);
    }

}