# Arup Guha
# 4/1/2026
# Solution to COP 4516 Contest Problem: Affine Cipher

def phi(n):

    i = 2
    res = n

    # Look for all unique prime factors.
    while i*i <= n:

        # See if i divides into n or not.
        div = False
        while n%i == 0:
            n //= i
            div = True

        # if it does, update our result.
        if div:
            res = res//i*(i-1)

        i += 1

    # Take care of last prime.
    if n > 1:
        res = res//n*(n-1)

    return res

# Process cases.
nC = int(input())
for loop in range(nC):

    # There are n choices for b, and phi(n) choices for a.
    n = int(input())
    print(n*phi(n))