#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define MOD 1000000009
 
ll dp[4][100002]; // dp[i][n] : i로 n을 만들수잇는 경우의 수
 
// 같은수를 "연속"해서 사용하면 안된다
// "연속" 을 체크해서 dfs를 구현한다
 
ll dfs(int num, int now) {
    if (num < 0) return 0;
    if (num == 0) return 1;
 
    ll& res = dp[now][num];
    if (res) return res;
 
    for (int i = 1; i <= 3; i++) {
        if (i != now) res += dfs(num - i, i)%MOD;
    }
 
    return res%MOD;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int num; cin >> num;
      
        cout << dfs(num, 0) << "\n";
    }
 
    return 0;
}