//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i++)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
cout << phi(x) << endl;
}
return 0;
}