#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

bool ciur[1000001];
int nr_pr[1000001];

void nr_prime(int n) {
    int k = 0;
    for (int i = 2; i <= n; ++i) {
        if (ciur[i] == 0) {
            nr_pr[k] = i;
            k++;
            for (int j = 2 * i; j <= n; j += i)
                ciur[j] = 1;
        }
    }
}

int main() {
    nr_prime(1000000);

    int m;
    fin >> m;
    for (int q = 0; q < m; ++q) {
        long long a, b;
        fin >> a >> b;
        int n = 0;
        long long v[101];
        int i = 0;
        while (b > 1 && nr_pr[i] * nr_pr[i] <= b) {
            if (b % nr_pr[i] == 0) {
                v[n++] = nr_pr[i];
                while (b % nr_pr[i] == 0)
                    b /= nr_pr[i];
            }
            i++;
        }
        if (b > 1) {
            v[n] = b;
            n++;
        }

        long long rez = a;
        for (int pij = 1; pij < (1 << n); ++pij) {
            long long p = 1, nrc = 0;
            for (int j = 0; j < n; ++j) {
                if (pij & (1 << j)) {
                    nrc++;
                    p *= v[j];
                    if (p > a) break;
                }
            }
            if (p <= a) {
                if (nrc % 2 == 1) rez -= a / p;
                else rez += a / p;
            }
        }

        fout << rez << endl;
    }

    return 0;
}