import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = list(range(num + 1))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        for j in range(i, num+1, i):
            min_factor_list[j] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)
