#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 32768 + 5;

int phi[maxn+5];

void phi_table(int n){

    memset(phi, 0, sizeof(phi));

    phi[1] = 1;

    for(int i = 2; i <= n; ++i)  if(!phi[i])

        for(int j = i; j <= n; j += i){

            if(!phi[j])  phi[j] = j;

            phi[j] = phi[j] / i * (i-1);

        }

}

int main(){

    phi_table(maxn);

    int n, T;  cin >> T;

    while(T--){

        scanf("%d", &n);

        printf("%d\n", phi[n]);

    }

    return 0;

}