Write a program to calculate the total number of strings that are made of exactly N characters.
None of the strings can have $“13”$ as a substring.
The strings may contain any integer from $0-9$, repeated any number of times.

Video approach to solve this question: here

Input Format
First line: T, the number of test cases.
Next T lines: Each contain an integer N.

Output Format
Print the result of each query $modulo 1000000009$.
Answer for each test case should come in a new line.

Constraints
$1 \le T \le 100000$
$0 \le N \le 1000000009$