import numpy as np

def generate_line(prev, row, max, doc, f):
    leng = len(prev)
    arr = [1]
    for i in range(leng - 1):
        i_ = prev[i] + prev[i + 1]
        if i_ <= max:
            arr.append(i_)
    if row % 2 == 0:
        if arr[-1] <= max:
            arr.append(arr[-1])
    for a in arr:
        if a in doc and doc[a] == -1:
            doc[a] = row
            f -= 1
    return arr, f


def main():
    n = int(input())
    f = n
    arr = []
    for i in range(n):
        arr.append(int(input()))
    abc = [1, 1]
    doc = dict()
    for c in arr:
        if c == 1:
            doc[c] = 1
            f -= 1
        else:
            doc[c] = -1
    i = 3
    while f != 0:
        abc, f = generate_line(abc, i, np.max(arr), doc, f)
        i += 1
    for a in arr:
        print(doc[a])


main()