F=[1]*7**6
for i in range(1,10):
 for j in range(i,7**6):F[j]+=F[j-i]
exec('print(F[int(input())//111111]%(10**9+9));'*int(input()))