#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

long long int t, a, b, n, k, p[1000005], A[1000005];
bitset<1000005> v;

int main() {
    for(int i = 2; i <= 1000000; i++) {
        if(!v[i]) {
            p[++n] = i;
            int j = 2;
            while(i * j <= 1000000) {
                v[i * j] = true;
                j++;
            }
        }
    }
    fin >> t;
    while(t > 0) {
        fin >> a >> b;
        long long int ans = a, k = 0;
        for(long long int i = 1; i * i <= b; i++) {
            if(b % p[i] == 0) {
				for(A[++k] = p[i]; b % p[i] == 0; b /= p[i]);
            }
        }
        if(b > 1) {
            A[++k] = b;
        }
        for(long long int i = 1; i < (1 << k); i++) {
            long long int r = 1, s = 0;
            for(long long int j = 0; j < k; j++) {
				if((i & (1 << j)) > 0) {
					s++;
					r *= A[j + 1];
				}
            }
            ans += ((s % 2 == 0 ? 1 : -1) * a / r);
        }
        fout << ans << "\n";
        t--;
    }
    fin.close();
    return 0;
}