/*
I n, n:(a)
数a的欧拉函数
O a的质数的个数

I
3
3
6
8

O
2
2
4
*/

#include <iostream>

using namespace std;


int phi(int x)
{
    int res = x;
    // 得到序列质数：2～x之间的i即为质数
    // i <= x / i : 1避免乘法溢出 2避免开方计算
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            // 欧拉公式换个写法：不溢出且不多省：res * (1 - 1 / i)
            res = res / i * (i - 1);
            // 完全消除质数：i^k，用循环
            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;
}