#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>

using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

const int SQRT_B = 1e6;
int q;
long long a, b;

bitset<(int)(1e6 + 5)> prim;
vector<int> primes, factors;

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

int main() {
    cin >> q;
    ciur();
    while (q--) {
        factors.clear();
        cin >> a >> b;
        // find b's prime factors
        int p_idx = 0;
        while (b > 1) {
            if (b % primes[p_idx] == 0) {
                factors.push_back(primes[p_idx]);
                while (b % primes[p_idx] == 0) b /= primes[p_idx];
            }
            if (1LL * primes[p_idx] * primes[p_idx] > b && b > 1) {
                factors.push_back(b);
                b = 1;
            }
            p_idx++;
        }
        long long sol = a;
        // use bitmask to get every single factor combination
        for (int i = 1 ; i < (1 << factors.size()) ; ++i) {
            long long lcm = 1;
            int cnt = 0;
            for (int j = 0 ; j < factors.size() ; ++j) {
                if ((1 << j) & i) {
                    // when working with primes, lcm is simply their product
                    lcm *= 1LL * factors[j];
                    ++cnt;
                }
            }
            int multiplier = ((cnt % 2) ? -1 : 1);
            // subtr. all div. by p1, p2, ..., add all div. by lcm(p1, p2), lcm(p1, p3), ..., subtr. all div by lcm(p1, p2, p3), ... ...
            sol += 1LL * multiplier * a / lcm;
        }
        cout << sol << "\n";
    }
    return 0;
}