#include <iostream>

using namespace std;

const int INF = 1e9;

long long pow(long long a, int n, long long m) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        long long half = pow(a, n / 2, m);
        return half * half % m;
    } else {
        return a * pow(a, n - 1, m) % m;
    }
}

int main()
{
    int t;
    cin >> t;
    for (; t > 0; --t) {
        long long a;
        long long m = 1e9 + 9;
        cin >> a;
        cout << pow(a, m - 1, m) - 1 << "\n";
    }

    return 0;
}