Problem Statement

$\mathcal{G}1$ and $\mathcal{G}2$ are almost the same problem, but they differ in constraints and time limit.

To commemorate this contest, Cherry-chan has decided to make an object that satisfies the following.

• $\Gamma_N$ is a regular $N$-gonal prism satisfying the following.
• Each base is a regular $N$-gon with side length $1$.
• Among the edges of the lateral faces, the edges connecting vertices of the 2 bases all have length $2$.
• All lateral faces are orthogonal to the bases.
• Each of the $2N$ vertices of $\Gamma_N$ is painted with $1$ color chosen from the $C$ colors, color $1, \dots,$ color $C$ (in this problem, $C=2$).

However, if she makes an object similar to one that already exists, she will get flamed on social media. Moreover, even if there is no such object now, if something similar appears later, she may get caught in the crossfire and things will become troublesome. Concerned about this, Cherry-chan became curious about how many objects can be made under the above conditions. Given $N, C$, find the answer to the following problem.

• How many colorings of the $2N$ vertices of $\Gamma_N$ are there, where colorings that coincide under rotation are not distinguished?

Answer for $T$ test cases (in this problem, $T=1$).

Constraints

• $T=1$
• $3 \leq N \leq 10$
• $C=2$
• All input values are integers.

Input

The input is given from standard input. Line $1$ of the input is in the following format.

$T$

$N$ $C$

Since $T=1, C=2$ are fixed in this problem, the entire standard input has the following form.

$1$
$N$ $2$

Output

The output consists of $T (=1)$ lines in total. On line $t~(1 \leq t \leq T=1)$, output the number of colorings of the $2N$ vertices of $\Gamma_N$ in the $t$-th test case, where colorings that coincide under rotation are not distinguished. Do not forget the trailing newline.

Sample

1
3 2

16