package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Number15990 {
private static final int MOD = 1_000_000_009;
private static long[][] cache;
private static int T, N;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
cache = new long[100_001][4];
cache[1][1] =1; // 1
cache[2][2] =1; // 2
cache[3][1] =1; // 2+1
cache[3][2] =1; // 1+2
cache[3][3] =1; // 3
for(int i = 4;i<100000;i++) {
cache[i][1] = (cache[i-1][2] + cache[i-1][3] % MOD); //cache[n]정수 n을 123의 합으로 나타내는 방법중 [1]이 가장 뒤에 오는 경우
cache[i][2] = (cache[i-2][1] + cache[i-2][3] % MOD);
cache[i][3] = (cache[i-3][1] + cache[i-3][2] % MOD);
}
T = Integer.parseInt(br.readLine()); //테스트 케이스의 개수
while(T-->0) { //T>0
N = Integer.parseInt(br.readLine());
long result = (cache[N][1] + cache[N][2] + cache[N][3]) % MOD;
sb.append(result).append("\n");
}
System.out.println(sb.toString());
}
}
JAVA