import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; import java.util.Scanner; import java.util.Set; public class Main { public static final long MOD = 1000000009; //public static int[] moneys = {111111, 222222, 333333, 444444, 555555, 666666, 777777, 888888, 999999}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); final int MAX = 1000000; final long[] DP = new long[MAX + 1]; Arrays.fill(DP, 1); for(final int money : new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}){ for(int i = 0; i <= MAX - money; i++){ DP[i + money] += DP[i]; DP[i + money] %= MOD; } } final int T = sc.nextInt(); for(int tt = 0; tt < T; tt++){ final long M = sc.nextLong(); final int dp_val = (int)(M / 111111); System.out.println((DP[dp_val]) % MOD); } } }