#!/usr/bin/env python
# -*- coding: utf-8 -*-

dp = [0 for i in range(10**5)]

for i in range(1,10):
    for j in range(10**5):
        if i+j < 10**5 and (dp[j] > 0 or j == 0):
            dp[i+j] += dp[j] + 1

T = int(input())
for _ in range(T):
    M = int(input())
    if M <= 111111:
        print(1)
    else:
        print((dp[M//111111] + 1)%(10**9+9))