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

const int BMAX = 1000000;

vector <int> primes;
bitset <BMAX> pr;
long long A, B;
int fact[BMAX];

inline void prime () {

    int i, j;
    primes.push_back (2);
    for (i = 3; i <= BMAX; i += 2) {
        if (!pr[i]) {
            primes.push_back (i);
            for (j = i << 1; j <= BMAX; j += i)
                pr[j] = 1;
        }
    }

}

inline long long pinex () {

    long long c, r = 0;
    int i, nr = 0, d = 0, lim, p;
    while (B > 1) {
        if (!(B % primes[d])) {
            fact[++nr] = primes[d];
            while (!(B % primes[d]))
                B /= primes[d];
        }
        if (primes[d] > sqrt (B) && B > 1) {
            fact[++nr] = B;
            break;
        }
        ++d;
    }
    lim = (1 << nr);
    for (i = 1; i < lim; ++i) {
        p = 0;
        c = 1;
        for (d = 0; d < nr; ++d)
            if ((i >> d) & 1) {
                ++p;
                c *= 1LL * fact[d + 1];
            }
        if (p & 1)
            r += A / c;
        else
            r -= A / c;
    }
    return A - r;

}

int main () {

    freopen ("pinex.in", "r", stdin);
    freopen ("pinex.out", "w", stdout);
    int Q;
    prime ();
    scanf ("%d", &Q);
    while (Q--) {
        scanf ("%lld%lld", &A, &B);
        printf ("%lld\n", pinex ());
    }

}