#include <bits/stdc++.h>

using namespace std;

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

vector <int> v;
long long s = 0;

void factoriPrimi (long long n)
{
    v.clear();
    long long k = n;
    for (int i = 2; i * i <= n && i <= k; i ++) {
        if (k % i == 0) {
            v.push_back(i);
            while (k % i == 0) k /= i;
        }
    }
    if (k != 1) v.push_back(k);
}

void combinari (int idx, int nr, long long product, long long a, int n)
{
    if (product > a) return;
    if (nr && nr % 2 == 0) s -= (a / product);
    else if (nr) s += (a / product);
    for (int i = idx; i < n; i ++) {
        product *= v[i], nr ++;
        combinari(i + 1, nr, product, a, n);
        product /= v[i], nr --;
    }
}

int main()
{
    int m;
    fin >> m;
    for (int j = 1; j <= m; j ++) {
        long long a, b;
        fin >> a >> b;
        factoriPrimi(b);
        int n = v.size();
        for (int i = 0; i < n; i ++) s += a / v[i];
        int idx = 0, nr = 0;
        long long product = 1;
        s = 0;
        combinari(idx, nr, product, a, n);
        fout << a - s << "\n";
    }
    return 0;
}