#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
template <size_t N>
class BigInt {/*{{{*/
private :
	uint32_t bit[N];
	uint32_t& operator [](size_t index) { return bit[index]; }
	const uint32_t& operator [](size_t index)const { return bit[index]; }
public :
	static constexpr size_t n = N;
	static bool sign(const BigInt &x) { return x[n - 1] & (1 << 31); }
	static BigInt StringToBigInt(const string &str) {
		BigInt res;
		size_t len = str.size(), start = 0;
		bool sgn = (str[0] == '-'); if(sgn) start = 1;
		for(size_t i = start; i < len; i++) {
			uint32_t carry = str[i] ^ 48;
			for(size_t j = 0; j < n; j++) {
				uint64_t temp = static_cast<uint64_t>(res[j]) * 10 + carry;
				res[j] = static_cast<uint32_t>(temp);
				carry = temp >> 32;
			}
		}
		return sgn ? -res : res;
	}
	static string BigIntToString(BigInt num) {
		bool sgn = sign(num);
		if(sgn) num = -num;
		vector<uint8_t> s;
		for(int i = n - 1; i >= 0; i--) {
			size_t m = s.size();
			uint32_t carry = num[i];
			for(size_t j = 0; j < m; j++) {
				uint64_t temp = (static_cast<uint64_t>(s[j]) << 32) + carry;
				s[j] = temp % 10;
				carry = temp / 10;
			}
			while(carry) s.emplace_back(carry % 10), carry /= 10;
		}
		string res;
	    for(auto it = s.rbegin(); it != s.rend(); ++it) res += (*it) ^ 48;
	    if(res.empty()) res = "0";
		return sgn ? '-' + res : res;
	}
  explicit operator int() const {
    auto str = BigIntToString(*this);
    int x;
    sscanf(str.c_str(), "%d", &x);
    return x;
  }
	BigInt() { memset(bit, 0, n * sizeof(uint32_t)); }
	BigInt operator ~() const { BigInt res; for(size_t i = 0; i < n; i++) res[i] = ~bit[i]; return res; }
	BigInt operator -() const {
		BigInt res = ~(*this);
		uint32_t carry = 1;
		for(size_t i = 0; i < n; i++) {
			uint64_t temp = static_cast<uint64_t>(res[i]) + carry;
			res[i] = static_cast<uint32_t>(temp);
			carry = temp >> 32;
		}
		return res;
	}
	BigInt(int x) {
		bool sgn = (x < 0); if(sgn) x = -x;
		bit[0] = x; memset(bit + 1, 0, (n - 1) * sizeof(uint32_t));
		if(sgn) *this = -(*this);
	}
	BigInt(long long x) {
		bool sgn = (x < 0); if(sgn) x = -x;
		bit[0] = x & 0xFFFFFFFF, bit[1] = x >> 32; memset(bit + 2, 0, (n - 2) * sizeof(uint32_t));
		if(sgn) *this = -(*this);
	}
	BigInt(const string &str) { *this = StringToBigInt(str); }
	friend istream& operator >> (istream &in, BigInt &x) { string str; in >> str; x = StringToBigInt(str); return in; }
	friend ostream& operator << (ostream &out, const BigInt &x) { out << BigIntToString(x); return out; }
	BigInt& operator &= (const BigInt &o) { for (size_t i = 0; i < n; i++) bit[i] &= o[i]; return *this; }
	BigInt operator & (const BigInt &o) const { BigInt res = *this; return res &= o; }
	BigInt& operator |= (const BigInt &o) { for (size_t i = 0; i < n; i++) bit[i] |= o[i]; return *this; }
	BigInt operator | (const BigInt &o) const { BigInt res = *this; return res |= o; }
	BigInt& operator ^= (const BigInt &o) { for (size_t i = 0; i < n; i++) bit[i] ^= o[i]; return *this; }
	BigInt operator ^ (const BigInt &o) const { BigInt res = *this; return res ^= o; }
	BigInt& operator <<= (size_t shift) {
	    if(shift == 0) return *this;
	    size_t wordShift = shift >> 5, bitShift = shift & 31;
	    if(wordShift >= n) { memset(bit, 0, sizeof(bit)); return *this; }
	    if(wordShift > 0) {
	        for(size_t i = n - 1; i >= wordShift; --i)
	            bit[i] = bit[i - wordShift];
	        memset(bit, 0, wordShift * sizeof(uint32_t));
	    }
	    if(bitShift > 0) {
	        for(size_t i = n - 1; i > 0; --i)
	            bit[i] = (bit[i] << bitShift) | (bit[i - 1] >> (32 - bitShift));
	        bit[0] <<= bitShift;
	    }
	    return *this;
	}
    BigInt& operator >>= (size_t shift) {
        if(shift == 0) return *this;
        size_t wordShift = shift >> 5, bitShift = shift & 31;
        if(wordShift >= n) { memset(bit, 0, sizeof(bit)); return *this; }
        if(wordShift > 0) {
            for(size_t i = 0; i < n - wordShift; ++i)
                bit[i] = bit[i + wordShift];
            memset(bit + n - wordShift, 0, wordShift * sizeof(uint32_t));
        }
        if(bitShift > 0) {
            for(size_t i = 0; i < n - 1; ++i)
                bit[i] = (bit[i] >> bitShift) | (bit[i + 1] << (32 - bitShift));
            bit[n - 1] >>= bitShift;
        }
        return *this;
    }
	BigInt operator << (const size_t &o) const { BigInt res = *this; return res <<= o; }
	BigInt operator >> (const size_t &o) const { BigInt res = *this; return res >>= o; }
	bool operator == (const BigInt &o) const {
		for(size_t i = 0; i < n; i++)
			if(bit[i] != o[i]) return false;
		return true;
	}
	bool operator != (const BigInt &o) const { return !(*this == o); }
    bool operator < (const BigInt &o) const {
		bool signT = sign(*this), signO = sign(o);
		if(signT != signO) return signT;
		for(int i = n - 1; i >= 0; i--)
			if(bit[i] != o[i]) return signT ? bit[i] > o[i] : bit[i] < o[i];
		return false;
	}
	bool operator > (const BigInt &o) const { return o < *this; }
	bool operator <= (const BigInt &o) const { return !(o < *this); }
	bool operator >= (const BigInt &o) const { return !(*this < o); }

	BigInt& operator += (const BigInt &o) {
		uint32_t carry = 0;
		for(size_t i = 0; i < n; i++) {
			uint64_t temp = static_cast<uint64_t>(bit[i]) + o[i] + carry;
			bit[i] = static_cast<uint32_t>(temp);
			carry = temp >> 32;
		}
		return *this;
	}
	BigInt operator + (const BigInt &o) const { BigInt res = *this; return res += o; }
	BigInt& operator -= (const BigInt &o) { *this += -o; return *this; }
	BigInt operator - (const BigInt &o) const { BigInt res = *this; return res += -o; }
    BigInt& operator ++ () { return *this += 1; }
	BigInt operator ++ (int) { BigInt res = *this; *this += 1; return res; }
	BigInt& operator -- () { return *this += -1; }
	BigInt operator -- (int) { BigInt res = *this; *this += -1; return res; }
	BigInt& operator *= (const BigInt &o) {
	    BigInt res;
	    for(size_t i = 0; i < n; i++) {
	        uint32_t carry = 0;
	        for(size_t j = 0; j + i < n; j++) {
	            uint64_t temp = static_cast<uint64_t>(bit[i]) * o[j] + res[i + j] + carry;
	            res[i + j] = static_cast<uint32_t>(temp);
	            carry = temp >> 32;
	        }
	    }
	    return *this = res;
	}
	BigInt operator * (const BigInt &o) const { BigInt res = *this; return res *= o; }
    BigInt& operator *= (const uint32_t &o) {
	    uint32_t carry = 0;
	    for(size_t i = 0; i < n; i++) {
	        uint64_t temp = static_cast<uint64_t>(bit[i]) * o + carry;
	        bit[i] = static_cast<uint32_t>(temp);
	        carry = temp >> 32;
	    }
	    return *this;
	}
	BigInt operator * (const uint32_t &o) const { BigInt res = *this; return res *= o; }
	BigInt& operator *= (int o) {
	    bool sgn = (o < 0); if(sgn) o = -o;
	    *this *= static_cast<uint32_t>(o);
	    if(sgn) *this = -(*this);
	    return *this;
	}
	BigInt operator * (const int &o) const { BigInt res = *this; return res *= o; }
    BigInt& operator /= (const BigInt &o) {
//		if(o == BigInt(0)) assert(false);
        bool sgn = sign(*this) ^ sign(o);
        if(sign(*this)) *this = -(*this);
        BigInt divisor = sign(o) ? -o : o;
        BigInt quotient, remainder;
        for(int i = (n << 5) - 1; i >= 0; --i) {
            remainder <<= 1;
            remainder[0] |= (bit[i >> 5] >> (i & 31)) & 1;
            if (remainder >= divisor) {
                remainder -= divisor;
                quotient[i >> 5] |= (1u << (i & 31));
            }
        }
        return *this = sgn ? -quotient : quotient;
    }
    BigInt operator / (const BigInt &o) const { BigInt res = *this; return res /= o; }
	BigInt& operator /= (const uint32_t &o) {
		bool sgn = sign(*this); if(sgn) *this = -(*this);
	    uint64_t carry = 0;
	    for(int i = n - 1; i >= 0; i--) {
	        uint64_t current = (carry << 32) | bit[i];
	        bit[i] = static_cast<uint32_t>(current / o);
	        carry = current % o;
	    }
	    if(sgn) *this = -(*this);
	    return *this;
	}
	BigInt operator / (const uint32_t &o) const { BigInt res = *this; return res /= o; }
	BigInt& operator /= (int o) {
	    bool sgn = (o < 0); if(sgn) o = -o;
	    *this /= static_cast<uint32_t>(o);
	    if(sgn) *this = -(*this);
	    return *this;
	}
	BigInt operator / (const int &o) const { BigInt res = *this; return res /= o; }
    BigInt& operator %= (const BigInt &o) {
//		if(o == BigInt(0)) assert(false);
        bool sgn = sign(*this);
        if(sign(*this)) *this = -(*this);
        BigInt divisor = sign(o) ? -o : o;
        BigInt quotient, remainder;
        for(int i = (n << 5) - 1; i >= 0; --i) {
            remainder <<= 1;
            remainder[0] |= (bit[i >> 5] >> (i & 31)) & 1;
            if (remainder >= divisor) remainder -= divisor;
        }
        return *this = sgn ? -remainder : remainder;
    }
    BigInt operator % (const BigInt &o) const { BigInt res = *this; return res %= o; }
	BigInt& operator %= (const uint32_t &o) {
		bool sgn = sign(*this); if(sgn) *this = -(*this);
	    uint32_t carry = 0;
	    for(int i = n - 1; i >= 0; i--) {
	        uint64_t current = (static_cast<uint64_t>(carry) << 32) | bit[i];
	        bit[i] = 0;
	        carry = current % o;
	    }
	    bit[0] = carry;
	    if(sgn) *this = -(*this);
	    return *this;
	}
	BigInt operator % (const uint32_t &o) const { BigInt res = *this; return res %= o; }
	BigInt& operator %= (int o) {
	    if (o < 0) o = -o;
	    *this %= static_cast<uint32_t>(o);
	    return *this;
	}
	BigInt operator % (const int &o) const { BigInt res = *this; return res %= o; }
};/*}}}*/
using mint = BigInt<9>;
mint operator*(int x, mint y) { return y * x; }
using LL = long long;
using FuncPtr = mint (*)(mint);
const FuncPtr F[] = {/*{{{*/
    +[](mint x) -> mint { return x; },
    +[](mint x) -> mint { return x * (x * x + 3 * x - 4) / 6; },
    +[](mint x) -> mint {
      return x *
             (5 * x * x * x * x * x * x + 35 * x * x * x * x * x +
              91 * x * x * x * x + 105 * x * x * x - 280 * x * x - 980 * x +
              1024) /
             1680;
    },
    +[](mint x) -> mint {
      return x *
             (429 * x * x * x * x * x * x * x * x * x * x * x * x * x * x +
              6435 * x * x * x * x * x * x * x * x * x * x * x * x * x +
              40425 * x * x * x * x * x * x * x * x * x * x * x * x +
              135135 * x * x * x * x * x * x * x * x * x * x * x +
              242151 * x * x * x * x * x * x * x * x * x * x +
              153153 * x * x * x * x * x * x * x * x * x -
              256685 * x * x * x * x * x * x * x * x -
              675675 * x * x * x * x * x * x * x -
              1606176 * x * x * x * x * x * x - 6846840 * x * x * x * x * x -
              16960944 * x * x * x * x - 19459440 * x * x * x +
              46382336 * x * x + 165065472 * x - 166219776) /
             276756480;
    },
}; /*}}}*/
const FuncPtr f[] = {/*{{{*/
    +[](mint x) -> mint { return 1; },
    +[](mint x) -> mint { return (x - 1) * (x + 2) / 2; },
    +[](mint x) -> mint {
      return (x - 1) * (x + 2) * (x * x + x - 4) * (x * x + x + 6) / 48;
    },
    +[](mint x) -> mint {
      return (x - 1) * (x + 2) * (x * x + x - 4) *
             (5 * x * x * x * x * x * x * x * x * x * x +
              25 * x * x * x * x * x * x * x * x * x +
              80 * x * x * x * x * x * x * x * x +
              170 * x * x * x * x * x * x * x + 289 * x * x * x * x * x * x +
              377 * x * x * x * x * x + 546 * x * x * x * x + 612 * x * x * x -
              3864 * x * x - 4128 * x - 26880) /
             215040;
    },
};/*}}}*/
constexpr int L = 1e6, N = L + 10;
mint q[N], preq[4][N];
int p[N];
mint P(mint n) {
  mint l = 0, r = mint(1) << (mint::n * 16 - 2), ans = 0;
  while (l <= r) {
    mint mid = (l + r) >> 1;
    if ((mid * (mid + 1) >> 1) <= n)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}
mint ns[110];
mint g(int c, int d) {
  if (ns[c] <= L) return preq[d][(int)ns[c]];
  return F[d](ns[c]) * g(c + 1, 0) - g(c + 1, d + 1);
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  q[1] = 1, p[1] = 1;
  int lst = 1;
  for (int i = 2; i <= L; i++) {
    if ((lst + 1) * (lst + 2) / 2 == i) ++lst;
    p[i] = lst;
    q[i] = q[i - 1] + q[lst];
  }
  for (int j = 0; j < 4; j++) {
    for (int i = 1; i <= L; i++) {
      preq[j][i] = preq[j][i - 1] + f[j](i) * q[p[i]];
    }
  }
  int t;
  cin >> t;
  while (t--) {
    cin >> ns[0];
    for (int i = 1; i <= 4; i++) ns[i] = P(ns[i - 1]);
    cout << g(0, 0) << endl;
  }
  return 0;
}