#include <fstream>
#include <vector>
#define int long long

using namespace std;

ifstream cin ("pinex.in");
ofstream cout ("pinex.out");

signed main() {
    int t;
    cin >> t;
    while(t--) {
        vector <int> v;
        int a, b;
        cin >> a >> b;
        int f = 2;
        while(b != 1) {
            int e = 0;
            while(b%f == 0)
                e++, b /= f;
            if(e)
                v.push_back(f);
            f++;
            if(f*f > b) {
                v.push_back(b);
                break;
            }
        }
        if(f > 1) {
            v.push_back(f);
        }
        int ans = 0;
        int n = v.size();
        for(int mask = 1; mask < (1<<n); mask++) {
            int card = 1, nrb = 0;
            for(int i = 0; i < n; i++) {
                if(mask & (1<<i))
                    card *= v[i], nrb++;
            }
            if(nrb%2 == 1)
                ans += (a/card);
            else ans -= (a/card);
        }
        cout << a-ans << '\n';
    }
}