#include<fstream>

using namespace std;
int m, nrp, nr, nrd;
long long a, b, aux, prod, r;
bool e[(int) 1e6 + 10];
int p[(int) 1e5 + 10], f[20], pr[20];

int main() {
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    for (int i = 2; i <= 1000010; i++) {
        if (e[i] == 0) {
            p[++nrp] = i;
            for (int j = i * 2; j <= 1000010; j += i) {
                e[j] = true;
            }
        }
    }
    fin >> m;
    for (; m; m--) {
        fin >> a >> b;
        aux = b;
        nrd = 0;
        for (int i = 1; i <= nrp && p[i] <= b / p[i]; i++) {
            if (b % p[i] == 0) {
                pr[++nrd] = p[i];
                while (aux % p[i] == 0) {
                    aux /= p[i];
                }
            }
        }
        if (aux != 1) {
            pr[++nrd] = aux;
        }
        r = 0;
        for (int i = 0; i <= nrd; i++) {
            f[i] = 0;
        }
        f[nrd] = 1;
        while (f[0] == 0) {
            nr = 0;
            prod = 1;
            for (int i = 1; i <= nrd; i++) {
                if (f[i] == 1) {
                    prod *= pr[i];
                    nr++;
                }
            }
            if (nr % 2 == 1) {
                r += a / prod;
            } else {
                r -= a / prod;
            }
            int j;
            for (j = nrd; f[j]; j--) {
                f[j] = 0;
            }
            f[j] = 1;
        }
        fout << a - r << "\n";
    }
    return 0;
}