#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
bool check[N];
int tot, p[N], f[N];
void init(){
    f[1] = 1;
    for (int i = 2; i < N; ++i){
        if(!check[i])    p[++tot] = i, f[i] = i - 1;
        for (int j = 1; j <= tot; ++j){
            if (i * p[j] > N - 3)    break;
            check[i * p[j]] = true;
            if (i % p[j] == 0) {
                f[i * p[j]] = f[i] * p[j];
                break;
            }
            else f[i * p[j]] = f[i] * (p[j] - 1);
        }
    }
}
int main() {
    int T;
    init();
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", f[n + 1]);
    }
    return 0;
}