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




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