#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;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKI2RlZmluZSBNT0QgMTAwMDAwMDAwOQogCmxsIGRwWzRdWzEwMDAwMl07IC8vIGRwW2ldW25dIDogaeuhnCBu7J2EIOunjOuTpOyImOyeh+uKlCDqsr3smrDsnZgg7IiYCiAKLy8g6rCZ7J2A7IiY66W8ICLsl7Dsho0i7ZW07IScIOyCrOyaqe2VmOuptCDslYjrkJzri6QKLy8gIuyXsOyGjSIg7J2EIOyytO2BrO2VtOyEnCBkZnPrpbwg6rWs7ZiE7ZWc64ukCiAKbGwgZGZzKGludCBudW0sIGludCBub3cpIHsKICAgIGlmIChudW0gPCAwKSByZXR1cm4gMDsKICAgIGlmIChudW0gPT0gMCkgcmV0dXJuIDE7CiAKICAgIGxsJiByZXMgPSBkcFtub3ddW251bV07CiAgICBpZiAocmVzKSByZXR1cm4gcmVzOwogCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSAzOyBpKyspIHsKICAgICAgICBpZiAoaSAhPSBub3cpIHJlcyArPSBkZnMobnVtIC0gaSwgaSklTU9EOwogICAgfQogCiAgICByZXR1cm4gcmVzJU1PRDsKfQogCmludCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCksIGNpbi50aWUoMCk7CiAgICBpbnQgVDsgY2luID4+IFQ7CiAgICB3aGlsZSAoVC0tKSB7CiAgICAgICAgaW50IG51bTsgY2luID4+IG51bTsKICAgICAgCiAgICAgICAgY291dCA8PCBkZnMobnVtLCAwKSA8PCAiXG4iOwogICAgfQogCiAgICByZXR1cm4gMDsKfQo=

MSAxMDAwMDA=

1 100000