#include <bits/stdc++.h>

using namespace std;

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

vector <int> v, prim;
bool fprim[1000005];
long long s = 0;

void ciur (int n)
{
    prim.push_back(2);
    for (int i = 3; i <= n; i += 2) {
        if (fprim[i] == 0) {
            prim.push_back(i);
            if (i * i <= n) {
                for (int j = i + i; j <= n; j += i) fprim[j] = 1;
            }
        }
    }
}

void factoriPrimi (long long n)
{
    v.clear();
    long long k = n;
    int m = prim.size();
    for (int i = 0; i < m && prim[i] * prim[i] < n && prim[i] <= k; i ++) {
        if (k % prim[i] == 0) {
            v.push_back(prim[i]);
            while (k % prim[i] == 0) k /= prim[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;
    ciur(1000000);
    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;
}