Lock Patterns and Spanning Trees

Android uses a pattern to lock a smartphone. The common lock pattern is a 3×3 grid of 9 nodes. Sanghyun wants stronger security, so he is building an app that offers the lock patterns described here.

In his app a lock pattern has a size from 2×2 up to $m \times m$, and only adjacent nodes can be connected. Two nodes are adjacent when one is directly next to the other horizontally, vertically, or diagonally. A node at one of the four corners is connected to 3 nodes, and every other node is connected to at most 8.

A lock pattern always has to form a spanning tree. A spanning tree is a set of edges of the graph that contains no closed loop. It also has to give a path between any two nodes, and it consists of $m^2 = n$ vertices and $n-1$ edges. A single lock pattern admits many different spanning trees.

To count the spanning trees of a graph $G$, first number every vertex $v_1, \dots, v_n$. Then build the matrix $T = [t_{ij}]$ this way.

• if $i = j$, then $t_{ij}$ is the number of edges incident to $v_i$
• if $i \ne j$, then $t_{ij}$ is $-1$ when there is an edge between $v_i$ and $v_j$, and $0$ when there is none

The number of spanning trees is a cofactor of $T$.

$\text{cofactor of } t_{ij} = (-1)^{i+j} M_{ij}$

Here $M_{ij}$ is the determinant of the $(n-1) \times (n-1)$ matrix obtained by deleting row $i$ and column $j$ from $T$. Every cofactor of $T$ has the same value, whichever $i$ and $j$ you pick.

For example, the matrix $T$ of the 2×2 pattern is as follows.

$T = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{pmatrix}$

Taking $i = 1$ and $j = 1$, the cofactor comes out like this.

$(-1)^{1+1} M_{11} = \begin{vmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{vmatrix} = 16$

So the 2×2 pattern has 16 spanning trees.

The matrix $T$ of the 3×3 pattern is as follows.

$T = \begin{pmatrix} 3&-1&0&-1&-1&0&0&0&0 \\ -1&5&-1&-1&-1&-1&0&0&0 \\ 0&-1&3&0&-1&-1&0&0&0 \\ -1&-1&0&5&-1&0&-1&-1&0 \\ -1&-1&-1&-1&8&-1&-1&-1&-1 \\ 0&-1&-1&0&-1&5&0&-1&-1 \\ 0&0&0&-1&-1&0&3&-1&0 \\ 0&0&0&-1&-1&-1&-1&5&-1 \\ 0&0&0&0&-1&-1&0&-1&3 \end{pmatrix}$

The cofactor of this matrix is the number of spanning trees of the 3×3 pattern.

Write a program that counts the spanning trees you can make on an $m \times m$ pattern.

The first line contains the number of test cases $N$ ($1 \le N \le 5$). Each of the next $N$ lines holds one test case, the pattern size $m$. ($2 \le m \le 6$)

For each test case, print on its own line the number of spanning trees you can make on the $m \times m$ pattern.

The $m = 2$ pattern is a graph of 4 vertices that are all connected to each other, and it has 16 spanning trees.