for _ in range(int(input())):
    p, q, r = 0, 0, 1
    for _ in range(int(input())):
        p, q, r = q, r, p + q + r
    print(r)