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

using namespace std;

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

const int NMAX = 10e6;

long long q, a, b;
int arr[NMAX + 10];
bitset < NMAX + 10 > prime;
vector < int > primeNr;

void doSieve() {

    primeNr.reserve(500);

    primeNr.push_back(2);
    prime[0] = prime[1] = 1;

    for(int i = 4;i <= NMAX;i += 2)
        prime[i] = 1;

    for(int i = 3;i + i <= NMAX;i += 2) {
        if (!prime[i]) {

            primeNr.push_back(i);

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

vector < int > getPrimeFactors(long long b) {

    vector < int > ret;

    ret.reserve(13);

    for(int i = 0;i < primeNr.size() && primeNr[i] <= b;++i) {
        if(b % primeNr[i] == 0)
            ret.push_back(primeNr[i]);
    }

    return ret;
}

long long prod{1}, sol{};
void back(int pos, vector < int >& factors) {

    int startPos = (pos == 1 ? 0 : arr[pos - 1] + 1);
    for(int i = startPos; i < factors.size();i++) {
        arr[pos] = i;
        prod *= factors[i];

        sol = sol + (pos % 2 == 1 ? (-1) * a / prod : a / prod);

        if(pos < factors.size())
            back(pos + 1, factors);

        prod /= factors[i];
    }
}

int main() {

    f >> q;

    doSieve();

    for(;q--;) {

        f >> a >> b;

        auto factors = getPrimeFactors(b);

        sol = a;
        prod = 1;
        back(1, factors);

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

    return 0;
}