#include <bits/stdc++.h>
using namespace std;
 
ifstream in("pinex.in");
ofstream out("pinex.out");
 
vector <long long> allPrimeFactors;
bitset <10000000> primeNumbers;
 
void generatePrimeFactors() {
    primeNumbers[1] = primeNumbers[0] = 1;
    for(int i = 2; i < 1100005; i++) {
        if(primeNumbers[i] == 1) continue;
        allPrimeFactors.push_back(i);
        for(int j = i + i; j < 1100005; j += i) {
            primeNumbers[j] = 1;
        }
    }
}
 
void solve(long long A, long long B) {
    vector <long long> itsPrimeFactors; /// B's prime factors
 
    long long cnt = 0;
    while(B > 1) {
        if(B % allPrimeFactors[cnt] == 0) {
            itsPrimeFactors.push_back(allPrimeFactors[cnt]);
            while(B % allPrimeFactors[cnt] == 0) {
                B /= allPrimeFactors[cnt];
            }
        }
        if(allPrimeFactors[cnt] * allPrimeFactors[cnt] > B && B != 1) {
            itsPrimeFactors.push_back(B);
            break;
        }
        ++cnt;
    }
    /**for(auto pf : itsPrimeFactors) {
        cout << pf << ' ';
    } **/
    long long best = 0, prod;
    for(int i = 1; i < (1 << itsPrimeFactors.size()); i++) {
        cnt = 0, prod = 1;
        for(int j = 0; j < itsPrimeFactors.size(); j++) {
            if((1 << j) & i) {
                ++cnt;
                prod *= itsPrimeFactors[j];
            }
        }
        (cnt & 1) == 1? cnt = -1 : cnt = 1;
        best = best + (A / prod) * cnt;
    }
    out << 1LL * (A + best) << '\n';
 
}
 
int main(void) {
    generatePrimeFactors();
    long long n, A, B;
    in >> n;
    while(n--) {
        in >> A >> B;
        solve(A, B);
    }
}