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.
Output:

For each test case, output one line containing the number of walks.

Constraints:

1<=n<=14