use proconio::*;
fn main(){
    input!{
        t: usize,
        l: [usize; t]
    }

    const MOD: usize = 1_000_000_009;
    const PARAM: usize = 111_111;
    let mx = *l.iter().max().unwrap() / PARAM;
    let mut dp = vec![1; mx+1];
    for i in 1..10{
        for j in i..=mx{
            dp[j]=(dp[j]+dp[j-i])%MOD;
        }
    }
    for i in l{
        println!("{}", dp[i/PARAM]);
    }
}