1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 int Ealer(int x)
 5 {
 6     int i,res = x;
 7     for(i=2;i<(int)sqrt(x*1.0)+1;i++)
 8         if(x%i==0){
 9             res = res / i * (i-1);
10             while(x%i==0)
11                 x/=i;    //保证i一定是素数
12         }
13     if(x>1) res = res/x*(x-1);
14     return res;
15 }
16 int main()
17 {
18     int cn;
19     cin>>cn;
20     while(cn--){
21         int n;
22         cin>>n;
23         cout<<Ealer(n)<<endl;
24     }
25     return 0;
26 }