EULER TOTIENT FUNCTION SPOJ SOLUTION

/*EULER TOTIENT FUNCTION SPOJ SOLUTION*/

#include<bits/stdc++.h>
using namespace std;
unsigned long long int etf(unsigned long long int n)
{ if(n==1)
 return 1;
       unsigned long long int ans=1,i;
       for(i=2;i*i<=n;i++)
       {
         if(!(n%i))
          {
          ans*=(i-1);
          n/=i;
          while(!(n%i)){ ans*=i;n/=i;}
         if(n==1)
          return (ans);
           }
       }
       return(ans*(n-1));
}
int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  unsigned long long int n;
  cin>>n;
  cout<<etf(n)<<"\n";
 }
return 0;
}