A bee larva living in a hexagonal cell of a large honey comb decides to creep 
for a walk. In each “step” the larva may move into any of the six adjacent cells
and after n steps, it is to end up in its original cell.
Your program has to compute, for a given n, the number of different such larva walks.

Input

The first line contains an integer giving the number of test cases to follow. 
Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14.
SAMPLE INPUT
2
2
4

Output

 
For each test case, output one line containing the number of walks. Under the
assumption 1 ≤ n ≤ 14, the answer will be less than 2^31.
SAMPLE OUTPUT
6
90