时间复杂度 $O(n\sqrt n)$

n = int(input())

def each(a):
    r = a
    i = 2
    while i <= a/i:
        s = 0
        while a%i ==0:
            s += 1
            a = int(a/i)
        if s != 0:
            r = r * (1-1/i)
        i += 1
    if a > 1:
        r = r * (1-1/a)
    return int(r)

while n:
    m = int(input())
    print(each(m))
    n -= 1