#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    //输入
    int n;
    cin >>n;

    while(n--)
    {
        int a;
        cin >> a;

        int res = a;
        for(int i = 2; i <= a/i;i++)
            if(a % i == 0) //i 是 a 的一个质因子
            {
                //公式放进来
                //N x(1- 1/p1)x(1-1/p2)x...x
                res = res /i * (i-1);
                //用循环把质因子剔干净
                while(a % i == 0) a/= i;
            }
        //如果a大于1，且有没有在if里执行，说明它是就是一个质数，直接处理它
        if(a > 1) res = res / a * (a-1);

        //res就是欧拉函数的值
        cout << res << endl;
    }
}