# Honeycomb Walk

A bee larva living in a hexagonal cell of a large honeycomb 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\leq n\leq 14$.

## Output

For each test case, output one line containing the number of walks. Under the assumption $1\le n\le 14$, the answer will be less than $2^{31}$.

Sample Input 1 Sample Output 1
2
2
4

6
90