p=10**9+9;N=90000;dp=[0]*(N+1);dp[0]=1;
for i in xrange(9):
	for j in xrange(N-i):dp[j+i+1]=(dp[j+i+1]+dp[j])%p
for i in xrange(N):dp[i+1]=(dp[i+1]+dp[i])%p
for i in xrange(input()):print dp[input()/111111]