import java.io.File;
import java.io.FileNotFoundException;
import java.rmi.MarshalledObject;
import java.util.Map;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * User: student
 * Date: 10.11.13
 * Time: 10:49
 * To change this template use File | Settings | File Templates.
 */
public class B {

    public static int unbreakable(int x) {
        if (x == 1)  return 1;
        if (x == 2) return 4;
        if (x % 2 == 0) return 3;
        return 2;
    }

    static int[] arr = new int[1001];


    public static int result(int n) {
        if (arr[n] != 0) {
            return arr[n];
        }

        int sum = unbreakable(n);

        for (int i = 1; i < n; i++) {
            sum += unbreakable(i) * result(n-i);
        }

        int res =  sum % 1000000009;
        arr[n] = res;
        return res;

    }

    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new File("STAIRS.IN"));

        for (int i = 0; i < arr.length; i++) {
            arr[i] = 0;
        }

        int T = scanner.nextInt();

        for (int i = 0; i < T; i++) {
            int N = scanner.nextInt();
            System.out.println(result(N));
        }
    }

}
