# 15990 - 1,2,3 더하기 5

# 9095 - 1,2,3 더하기와 다른 점은 같은 수를 두 번 이상 연속해서 사용하면 안된다는 것이다.
# 연속을 처리하는 것이 핵심이다.
# d[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j (j의 최대 값은 3)
# d[i][1] => 바로 전에 사용할 수 있는 수는 2,3  = d[i-1][2] + d[i-1][3]
# d[i][3] => 바로 전에 사용할 수 있는 수는 1,2  = d[i-1][1] + d[i-1][2]

limit = 100000  # n 제한
mod = 1000000009
d = [[0 for col in range(4)] for row in range(limit + 1)]

d[1][1] = 1
d[2][2] = 1
d[3][1] = d[3][2] = d[3][3] = 1 #  2 + 1,  1 + 2, 3

for i in range(4, limit + 1):
    d[i][1] = (d[i - 1][2] + d[i - 1][3]) % mod  # 2, 3으로 끝난 d-1에 1을 더한 것이 현재의 d[i][1]
    d[i][2] = (d[i - 2][1] + d[i - 2][3]) % mod  # 1, 3으로 끝난 d-2에 2을 더한 것이 현재의 d[i][2]
    d[i][3] = (d[i - 3][1] + d[i - 3][2]) % mod  # 1, 2으로 끝난 d-3에 3을 더한 것이 현재의 d[i][3]

t = int(input())
for _ in range(t):
    n = int(input())
    print(sum(d[n]) % mod)  # d[n][0] + d[n][1] + d[n][2] + d[n][3]
