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

#define int long long
int factori[21];
// int desc[21];

signed main() {
    int q;
    cin >> q;
    while(q--) {
        int a, b;
        cin >> a >> b;
        //descompunem b in factori prim
        int nr = 0;
        for(int d = 2; d * d <= b; d++) {
            if(b % d == 0) {
                nr++;
                factori[nr] = d;
                while(b % d == 0) {
                    b /= d;
                }
            }
        }
        if(b > 1) {
            nr++;
            factori[nr] = b;
        }
        int res = 0;
        for(int i = 1; i <= (1 << nr) - 1; i++) {
            int cnt = 0;
            int b1 = 0;
            int prod = 1;
            int x = i;
            while(x > 0) {
                cnt++;
                //desc[cnt] = x % 2;
                if(x % 2) {
                    b1++;
                    prod = prod * factori[cnt];
                }
                x /= 2;
            }
            if(b1 % 2) {
                res += a / prod;
            } else {
                res -= a / prod;
            }
        }
        cout << a - res << '\n';
    }
    return 0;
}