Description

一环上有n个节点，分别被标号为0, 1, ..., n-1。有一人初始在0处。当人在x处时，可以移动到(x+1)%n, (x+2)%n, (x-1+n)%n或(x-2+n)%n处。求经过每个格子恰好一次且最终回到0处的方案数。答案模1000000009。

Format

Input

第一行，一个整数t，表示询问个数。

下面t行，每行一个整数n。

Output

对于每个询问，输出一行，表示对应的答案。

Samples

5
5
6
7
8
9

12
16
23
29
41

Hint 50%的数据 t<=1000 n<=100000

70%的数据 t<=10000

100%的数据 t<=100000 5<=n<=10^18