#include <fstream>
#include <vector>
using namespace std;

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

typedef unsigned long long ull;

ull a, b;
int n, sol = 0;
vector <ull> v;

int main() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        vector <ull>().swap (v);
        fin >> a >> b;
        if (b % 2 == 0) {
            while (b % 2 == 0)
                b /= 2;
            v.push_back (2);
        }
        int aux = b;
        for (ull i = 3; i * i <= aux && b != 1; ++i)
            if (b % i == 0) {
                v.push_back (i);
                while (b % i == 0)
                    b /= i;
            }
        if (b != 1)
            v.push_back (b);
        sol = 0;
        int k = v.size();
        for (int i = 1; i < (1 << k); ++i) {
            ull prod = 1, nr = 0;
            for (int j = 0; j < k; ++j)
                if (i & (1 << j)) {
                    prod *= v[j];
                    nr++;
                }
            if (nr % 2)
                sol += a / prod;
            else
                sol -= a / prod;
        }
        fout << a - sol << "\n";
    }
}