Problem

Taro lives in the Land of Six-in-a-Row.
In this country, a total of \(10\) types of coins are used: the \(1\)-yen coin, plus coins whose values are repdigits made of \(6\) digits, that is, the \(111111\)-yen coin, the \(222222\)-yen coin, …, and the \(999999\)-yen coin.

Piggy Bank has saved up coins and saved up more, and now holds at least \(10^{20}\) coins of every type.
However, Taro wanted to go shopping for \(M\) yen.
Taro asked Piggy Bank to give him coins totaling exactly \(M\) yen.
Piggy Bank, reluctant to give away the coins he had worked so hard to save, decided to give them only if Taro could answer a question.
Piggy Bank asked, "What is the minimum number of coins I must hand over to give you \(M\) yen?", but Taro answered instantly.
So Piggy Bank switched to one more question: "How many ways are there for me to hand over coins to give you \(M\) yen?"
This time, Taro was stumped.
Write a program that finds the number of ways Piggy Bank can hand \(M\) yen to Taro, modulo \(10^9+9\).

Input

\(T\)
\(M_1\)
\(M_2\)
\(\vdots\)
\(M_T\)

\(1 \leq T \leq 10000\) denotes the number of test cases.
\(1 \leq M_k \leq 10^{10}\) denotes the value of \(M\) in each test case.

Output

On the \(k\)-th line of the output, print the number of ways Piggy Bank can hand \(M_k\) yen to Taro, modulo \(10^9+9\).

Sample

7
1
111112
222222
10000000
100000000
1000000000
10000000000

1
2
4
21312056
818664350
50564368
385490639