T = int(input())
for case in range(T):
    N = int(input())
    P = {}
    for i in range(2, int(N ** 0.5) + 1):
        if N % i == 0:
            while N % i == 0:
                N //= i
                P[i] = P.get(i, 0) + 1
    if N != 1:
        P[N] = P.get(N, 0) + 1
    ans = 1
    for k in P.keys():
        if k > 5:
            ans *= (k - 1)
    print(ans)