BAEKJOON_15990

import java.io.*;
import java.sql.Array;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int test_case = Integer.parseInt(br.readLine());
        int[][] d;
        for(int t=1; t<=test_case; t++){
            int N = Integer.parseInt(br.readLine());

            d = new int[N+1][N+1];

            for(int i=1; i<=N; i++){
                if(i-1 >=0){
                    d[i][1] = d[i-1][2] + d[i-1][3];
                    if(i==1){
                        d[i][1]=1;
                    }
                }

                if(i-2>=0){
                    d[i][2] = d[i-2][1] + d[i-2][3];
                    if(i==2){
                        d[i][2]=1;
                    }
                }

                if(i-3>=0){
                    d[i][3] = d[i-3][1] + d[i-3][2];
                    if(i==3){
                        d[i][3] =1;
                    }
                }

                d[i][1] = d[i][1] % 1000000009;
                d[i][2] = d[i][2] % 1000000009;
                d[i][3] = d[i][3] % 1000000009;
            }
            bw.write(String.valueOf(d[N][1] + d[N][2] + d[N][3]));
            bw.flush();
        }
        bw.close();

    }

}