#include <bits/stdc++.h>

using namespace std;

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

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

int main() {
    for(int i = 2; i * 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;
        int ans = a, k = 0;
        for(int i = 1; i * i <= b; i++) {
            if(b % p[i] == 0) {
				while(b % p[i] == 0) {
				    A[++k] = p[i];
				    b /= p[i];
				}
            }
        }
        if(b > 1) {
            A[++k] = b;
        }
        for(int i = 1; i < (1 << k); i++) {
            int r = 1, s = 0;
            for(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;
}