BAEKJOON_15988

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());

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

            for(int i=3; i<=N; i++){
                d[i] = d[i-1]+d[i-2]+d[i-3];
                d[i]%=1000000009;
            }

            bw.write(String.valueOf(d[N]));
            bw.newLine();
            bw.flush();
        }
        bw.close();
    }
}