무릎 문제 (쉬움)

어두운 던전을 헤맨다. 주변에는 모양과 색이 제각각인 문들이 늘어서 있다. 그중 하나를 골라 열고 안으로 들어간다.

"네가 올 줄 알았다." 어둠 속에서 목소리가 들린다. 가까이 다가가 보니 긴 흰 수염의 노인이 바닥에 앉아 있다.

"나도 예전에는 너처럼 문제를 푸는 사람이었지. 그런데 무릎에 화살을 맞고 말았어."

"정말이에요?" 하고 묻는다.

"글쎄, 사실 그렇지는 않아. 내가 마지막으로 햇빛을 본 때에 아이들이 그렇게 떠들고 다녔을 뿐이야."

"그럼 어떻게 된 일인가요?" 하고 물으며 노인 옆에 앉는다.

"솔직히 말하면, 계단에서 무릎뼈를 망가뜨렸어. 젊었을 때는 프로그래밍 대회에 자주 나갔지. 그중 한 대회에 정말 골치 아픈 문제가 있었어. n개의 계단으로 된 계단을 오르내리는 방법의 수를 구하는 문제였지. 물론 조건이 있었어. 올라갈 때는 한 번에 두 칸씩 갈 수 있고, 내려올 때는 한 번에 최대 네 칸까지 갈 수 있었지."

노인은 깊게 한숨을 쉰다. "그 문제를 어떻게 풀어야 할지 전혀 몰랐어. 그래서 계단을 찾아가 가능한 경우를 전부 시도해 보려고 했지. 그런데 경우가 너무 많아서 무릎에 무리가 가고 말았다네. 지금은 걷지도 못해. 그래서 여기 앉아서 아직도 그 문제의 풀이를 고민하고 있지. 이제 이 일을 끝낼 수 있도록 도와주겠나?"

계단은 n개의 칸으로 이루어져 있다. 다음 조건에 따라 계단을 올라갔다가 내려오는 방법의 수를 세어라.

• 올라갈 때는 한 번에 1칸 또는 2칸씩 갈 수 있다.
• 내려올 때는 한 번에 1칸, 2칸, 3칸, 또는 4칸씩 갈 수 있다.

실제 방법의 수는 매우 클 수 있으므로, 그 값을 $10^9 + 9$로 나눈 나머지를 구하라.

예를 들어 $n = 5$일 때, 계단을 오르내리는 유효한 방법 하나는 다음과 같다. 땅에서 출발해 2번 칸까지 올라가고, 3번 칸을 거쳐 5번 칸까지 간다. 꼭대기에 도착하면 몸을 돌려 내려가는데, 먼저 4번 칸까지 내려간 뒤 곧바로 땅으로 내려간다. 이때 땅은 4칸 아래에 있다.

위 그림은 $n = 5$일 때 계단을 오르내리는 유효한 방법 두 가지를 보여 준다. 위에서 설명한 방법은 빨간색으로 표시되어 있다.

입력의 첫 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다.

각 테스트 케이스는 계단의 칸 수를 나타내는 정수 $n$($1 \le n \le 100{,}000$)이 적힌 한 줄로 이루어진다.

각 테스트 케이스에 대해, 유효한 방법의 수를 $10^9 + 9$로 나눈 나머지를 한 줄에 정수 하나로 출력하라.

예를 들어 $n = 3$일 때, 올라가는 방법은 3가지이고 각각에 대해 내려오는 방법은 4가지이다.