import sys
input=lambda:sys.stdin.readline().rstrip()
mod=10**9+9
N=int(input())
M=[int(input())//111111 for i in range(N)]
rang=max(M)
dp=[[1 for i in range(rang+1)] for j in range(9)]
for i in range(1,9):
	for j in range(i+1):
		dp[i][j]=dp[i-1][j]
	for j in range(i+1,rang+1):
		dp[i][j]=(dp[i-1][j]+dp[i][j-i-1])%mod
for i in range(rang):
	dp[8][i+1]=(dp[8][i+1]+dp[8][i])%mod
for i in M:
	print(dp[8][i])