#include <iostream>
#include <vector>
#include <cmath>
#define int long long
using namespace std;

signed main() {
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t; cin >> t;
    while(t --) {
        int a, b; cin >> a >> b;
        vector<int> div;
        for(int i(2); i <= b; i ++) {
            if(b % i == 0) {
                div.push_back(i);
                // cout << i << ' ';
            }
            while(b % i == 0) {
                b /= i;
            }
            if(i >= sqrt(b)) {
                div.push_back(b);
                // cout << b << ' ';
                break;
            }
        }
        int ans = 0;
        for(int mask(1); mask <= (1 << (div.size())) - 1; mask ++) {
            int popcnt = __builtin_popcount(mask);
            int sum(1);
            for(int i = 0; i < div.size(); i ++) {
                if((mask & (1 << i)) == 0)
                    continue;
                sum *= 1ll * div[i];
            }
            if(popcnt % 2) {
                ans += a / sum;
            } else {
                ans -= a / sum;
            }
        }
        cout << a - ans << '\n';
    }
}