e-olymp
Problems

Honeycomb Walk

Honeycomb Walk

prb1284 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 the number of test cases to follow. Each case consists of one line containing an integer n (1n14).

Output

For each test case, print one line containing the number of walks. Under the assumption 1n14, the answer will be less than 231.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
2
2
4
Output example #1
6
90
Source 2006 Nordic Collegiate Programming Contest, September 30, Problem I