#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

const int NMAX = 10e6;

int q;
bitset < NMAX + 10 > isPrime;
vector < int > primes;

void doSieve() {

    isPrime[0] = isPrime[1] = 1;

    for(int i = 2;i + i <= NMAX;i += (i == 2 ? 1 : 2)) {
        if (!isPrime[i]) {

            primes.push_back(i);

            for(int j = i + i;j <= NMAX;j += i)
                isPrime[j] = 1;
        }
    }
}

vector < int > getPrimeFactors(long long nr) {

    vector < int > ret;

    for(int i = 0;i < primes.size() && primes[i] * primes[i] <= nr;++i) {
        if(nr % primes[i] == 0) {
            ret.push_back(primes[i]);
            for(;nr % primes[i] == 0; nr /= primes[i]);
        }
    }

    if(nr > 1)
        ret.push_back(nr);

    return ret;
}

int main() {

    doSieve();

    for(f >> q;q--;) {

        long long a, b;
        f >> a >> b;

        auto factors = getPrimeFactors(b);

        long long lim = (1 << factors.size()) - 1;
        long long sol = a;

        for(long long mask = 1;mask <= lim;++mask) {

            int counter{};
            long long prod{ 1 };

            for(int i = 0;i < factors.size();++i) {
                if(((mask >> i) & 1) == 1) {// the bit at position i is one
                    counter++;
                    prod *= factors[i];
                }
            }

            if(counter > 0)
                sol = sol + (counter % 2 == 1 ? -1 * a / prod : a / prod);
        }

        g << sol  << '\n';
    }

    return 0;
}