import itertools import sys def input(): return sys.stdin.readline().rstrip() def main(): R = 111111 M = 10**10 // R MOD = 10**9 + 9 S = [1]+[0]*M for i in range(1, 10): for j in range(M-i+1): S[j+i] = (S[j+i] + S[j]) % MOD *S, = itertools.accumulate(S) T = int(input()) for i in range(T): print(S[int(input()) // R] % MOD) if __name__ == '__main__': main()