#include <fstream>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

bool neprim[1000005];
int np[80005], nr, i, t;

void ciur() {
    int i, j;

    nr = 1;
    np[1] = 2;
    for (i = 3; i <= 1000000; i += 2)
        if (neprim[i] == 0) {
            np[++nr] = i;
            for (j = 3*i; j <= 1000000; j += 2*i)
                neprim[j] = 1;
        }
}

long long rezolva() {
    long long a, b;
    f >> a >> b;
    int i = 1;

    int fac[13], nf = 0;

    while (b > 1) {
        if (np[i]*np[i] > b) {
            fac[nf++] = b;
            b = 1;
        }
        else if (b%np[i] == 0) {
            fac[nf++] = np[i];
            while (b%np[i] == 0)
                b /= np[i];
        }
        i++;
    }

    int j, nr;
    long long prod, sol = 0, fin;

    for (i = 1; i < (1<<nf); i++) {
        prod = 1;
        nr = 0;
        for (j = 0; j < nf; j++)
            if ( (i&(1<<j)) != 0 )
                nr++, prod *= fac[j];

        if (nr%2 == 1)
            sol += a/prod;
        else sol -= a/prod;
    }
    fin = a-sol;
    return fin;
}

int main() {
    f >> t;
    ciur();
    for (i = 1; i <= t; i++)
        g << rezolva() << '\n';

    return 0;
}