import strutils,sequtils,algorithm



var
    T = stdin.readline.parseInt
    M : int64
    m : int
    dp : array[100000,int]
    mmod = 1_000_000_009
for i in 0..<100000:
    dp[i] = 1
for i in 1..9:
    for j in 0..90000:
        dp[j + i] = (dp[j] + dp[j + i]) mod mmod
for t in 0..<T:
    M = stdin.readline.parseBiggestInt
    m = (M div 111_111).int
    echo dp[m]