#include <iostream>

 #include <cstring>

 #include <cmath>

 #include <cstdio>

 #include <iomanip>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int MAXN = ;

 const int MOD = 1e9+;

 int euler(int n)

 {

     int ret = n;

     for(int i = ;i * i <= n;++i)

     {

         if(n % i == )

         {

             ret = ret - ret / i;

             while(n % i == )

                 n /= i;

         }

     }

     if(n > )

         ret = ret - ret / n;

     return ret;

 }

 int main()

 {

     int T;

     cin >>T;

     while(T--)

     {

         int n;

         cin >>n;

         cout <<euler(n)<<endl;

     }

     return ;

 }