mod=10**9+9 DP=[[0]*10 for i in range(10**5)] for i in range(10**5): DP[i][0]=1 for i in range(10**5-10): for j in range(1,10): for k in range(j+1): if i-j>=0: DP[i][j]+=DP[i-j][k] DP[i][j]%=mod T=int(input()) for tests in range(T): N=int(input()) N//=111111 print(sum(DP[N])%mod)