DJ Boy is a new generation child he has never seen numeric keypad of mobile. So one day when Prem showed him his mobile, DJ boy started laughing on him. Prem being smart gave him a problem to solve with some condition. Your task is to help DJ boy to solve this problem:

Given a number N, DJ boy has to tell how many numbers of length N are possible.

Conditions:

1)He can only press digit that are adjacent i.e. to the left, right, up or bottom to current digit.

2)He may press the same key again i.e. numbers like 000 & 080 are possible for length 3.

3)He cannot press * and # keys.

Constraints:

1 ≤ t ≤ 100

0 ≤ N ≤ 10000

MOD: 10^9 + 9

Input:

First line contains T,the number of test cases.
Next t lines contain a number N.

Output:

Print the required number modulo MOD.

SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
10
36

见题面

见题面