#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
	int q;
    cin >> q;
    while(q--) {
        int a, b;
        cin >> a >> b;
        vector<int> factori;
        for(int d = 2; d * d <= b; d++) {
            if(b % d == 0) {
                factori.push_back(d);
                while(b % d == 0) {
                    b /= d;
                }
            }
        }
        if(b > 1) {
            factori.push_back(b);
        }
        int n = factori.size();
        int sol = 0;
        for(int i = 1; i < (1 << n); i++) {
            int prod = 1;
            int nr = 0;
            for(int j = 0; (1 << j) <= i; j++) {
                if((1 << j) & i) {
                    prod *= factori[j];
                    nr++;
                }
            }
            if(nr % 2) {
                sol += a / prod;
            } else {
                sol -= a / prod;
            }
        }
        cout << a - sol << '\n'
    }
    return 0;
}