Jumping Zippy likes to jump. He jumps every day and feels boring. Then he think of a new way to jump. He jumps on a big round plaza. The plaza is divided into n sectors numbered clockwise from 0 to n-1. Firstly, he stands on sector 0. Each time, when he is stand on sector x, he can jump to sector (x-2)%n, (x-1)%n, (x+1)%n or (x+2)%n. His goal is to jump to each sector exactly once and jump back to sector 0 at last. And for the first jump, he never jumps to sector n-1 or sector n-2. He wants to find the number of different ways in which he can complete his goal.

Input

First line is a number t, which is the number of test cases. (1 ≤ t ≤ 1000)

Then following t lines, each line contains a integer n, which is the number of sectors. (5 ≤ n ≤ 10¹⁸)

Output

For each query n, output a line which contains one integer, the number of different ways Zippy can complete his goal in, modulo 10⁹+9.

Example

Input:
5
5
6
7
8
9

Output:
12
16
23
29
41