with open('input.txt') as f:
    n = int(f.readline())
    a = [int(i) for i in f.readline().split()]

calculated = dict()

def rec(position):
    if position == 0:
        return 0
    if position == 1:
        return 1
    if position == 2:
        return 2
    i = 3
    last1 = 2
    last2 = 1
    last3 = 0
    while i <= position:
        result = last1 + last3
        last3 = last2
        last2 = last1
        last1 = result
        calculated[i] = result
        i+=1
    return result

with open("output.txt", "w") as f:
    for i in range(len(a)):
        if a[i] in calculated:
            if i != len(a)-1:
                f.write(str(calculated[a[i]])+' ')
            else:
                f.write(str(calculated[a[i]]))
        else:
            if i != len(a)-1:
                f.write(str(rec(a[i]))+' ')
            else:
                f.write(str(rec(a[i])))