#include<iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    while (n--) {
        int a;
        cin >> a;

        int res = a;

        // 欧拉函数 N * (1 - 1 / p1) * ···
        for (int i = 2; i <= a / i; i++) {
            if (a % i == 0) {
                res = res / i * (i - 1);    // 为避免小数误差
                while (a % i == 0) a /= i;
            }
        }
        if (a > 1) res = res / a * (a - 1); // a > 1 时还有一个本身

        cout << res << endl;
    }
}