1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 33000 6 int is_prime[N], prime[N], phi[N]; 7  8 void Euler() { 9     int n = 32767;10     phi[1] = 0; int cnt = 0;11     for(int i = 2; i <= n; i++) {12         if(!is_prime[i]){13             prime[++cnt] = i; phi[i] = i - 1;14         }15         for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {16             is_prime[i * prime[j]] = 1;17             if(i % prime[j] == 0) {18                 phi[i * prime[j]] = phi[i] * prime[j];19                 break;20             }21             phi[i * prime[j]] = phi[i] * phi[prime[j]];22         }23     }24 }25 26 int main() {27     int t;28     scanf("%d", &t);29     Euler();30     while(t--) {31         int n;32         scanf("%d", &n);33         printf("%d\n", phi[n]);34     }35     return 0;36 }