Competitions

# DSCS 2013 Triangular and hexagonal grid. Part 2

# 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 ﬁrst line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integer **n** (**1** ≤ **n** ≤ **14**).

**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}**.

Input example #1

2 2 4

Output example #1

6 90