Till innehållet
Meny

Utvecklare på IT.

Lös uppgiften och skicka in ditt program som ska kunna läsas från standard input, och skriva sitt svar på standard output, input kommer att motsvara det som finns i specifikationen på uppgiften. Du kan skriva ditt program i Java, C++, C, C#, Go, Objective-C eller Python 2.

Mailadress:
puzzle@tre.puzzle.scrool.se.
Ämnesrad: Skriv uppgiftens namn Honeycomb Walk
Ange: ditt namn och den mailadress du vill bli kontaktad på

Honeycomb Walk

Problem ID: honey

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