SPOJ in Gyumri

   There is a garden on the hillside, near one of the Alliance of Combinatorics Masters’s (ACM) building. Hill is steep, so each and every road in garden technically is a long stone stairs. Each step of the stairs has rectangular shape; all of them are paved with tiles – 1x2 rectangles. Width W of every step is 4, length N may vary.

   During usual walk one of the Masters found three steps of same size, paved in different ways. Now Master wonders, how many different ways there is to pave a step of known size. Please, help him find the answer.

Input

   First line of input file contains single number T (T ≤ 200) – number of test cases. Next T lines contain T test cases; each test case consists of single number N (1 ≤ N ≤ 10³) – length of the step. Width of each step is fixed – 4.

Output

   For each test case print in different line single number – number of different ways of paving step Nx4; answer can be pretty big, so print it modulo 1 000 000 009

Examples