'''
套欧拉函数公式即可
'''

import math

n = int(input())
for _ in range(n):
    val = int(input())

    ans = val
    for i in range(2, int(math.sqrt(val)) + 1):
        if val % i == 0:
            while val % i == 0:
                val //= i

            ans = ans // i * (i-1)

        if val == 1:
            break

    # 特判最后可能剩下的大于sqrt(val)的最大的质因子
    if val != 1:
        ans = ans // val * (val - 1)
    print(ans)