import sys
input=lambda:sys.stdin.readline().rstrip()
mod=10**9+9
C=[[i==0 for i in range(6)] for j in range(6)]
for i in range(1,6):
	for j in range(1,6):
		C[i][j]=C[i-1][j]+C[i-1][j-1]
def inv(a):
	ans=1
	temp=a
	rem=mod-2
	while rem:
		if rem%2:
			ans=(ans*temp)%mod
		temp=(temp**2)%mod
		rem//=2
	return ans
S=[[1,1,0,0,0,0],[0,inv(2),inv(2),0,0,0],[0,inv(6),inv(2),inv(3),0,0],[0,0,inv(4),inv(2),inv(4),0],[0,-inv(30),0,inv(3),inv(2),inv(5)]]
coins=[500,100,50,10,5,1]
def s(poly):
	ans=[0,0,0,0,0,0]
	for i in range(5):
		for j in range(6):
			ans[j]=(ans[j]+poly[i]*S[i][j])%mod
	return ans
def sub(poly,poly2):
	ans=[0,0,0,0,0,0]
	for i in range(6):
		for j in range(i+1):
			ans[j]=(ans[j]+poly[i]*C[i][j]*poly2[1]**j*poly2[0]**(i-j))%mod
	return ans
def solve(M):
	poly=[1,0,0,0,0,0]
	a=[0 for i in range(5)]
	for i in range(5):
		a[4-i]=M//coins[i]
		M%=coins[i]
	for i in range(5):
		poly=s(poly)
		poly=sub(poly,[a[i],[2,5][i%2]])
	print(poly[0])
N=int(input())
for i in range(N):
	solve(int(input()))