#include <bits/stdc++.h>

using namespace std;

int main() {
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    int t;
    f >> t;
    while(t--) {
        long long a, b;
        f >> a >> b;
        vector<long long> factoriPrimiB;
        for(long long fact = 2; fact * fact <= b; fact++) {
            if(b % fact == 0) {
                factoriPrimiB.push_back(fact);
                while(b % fact == 0) {
                    b /= fact;
                }
            }
        }
        if(b > 1) {
            factoriPrimiB.push_back(b);
        }
        int n = factoriPrimiB.size();
        long long sol = 0;
        for(int i = 1; i <= (1 << n) - 1; i++) {
            vector<int> bits;
            int x = i;
            while(x > 0) {
                bits.push_back(x % 2);
                x /= 2;
            }
            //reverse(bits.begin(), bits.end());
            long long prod = 1;
            int cnt = 0;
            for(int i = 0; i < bits.size(); i++) {
                //cout << bits[i] << ' ';
                if(bits[i] == 1) {
                    cnt++;
                    prod *= factoriPrimiB[i];
                }
            }
            if(cnt % 2 == 0) {
                sol -= a / prod;
            } else {
                sol += a / prod;
            }
        }
        //cout << sol << ' ';
        g << a - sol << '\n';
    }
    return 0;
}