def proper_fractions(n):
    if n == 1: return n
    phi = n
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    if n > 1: phi -= phi // n
    return phi

n = input()

for it in range(int(n)):
    s = input()
    a = int(s)
    print(proper_fractions(a))