잠금 패턴과 스패닝 트리

안드로이드는 스마트폰을 잠글 때 패턴을 쓴다. 흔히 쓰는 잠금 패턴은 3×3 그리드에 노드 9개로 이루어져 있다. 상현이는 보안을 더 높이려고 다음과 같은 잠금 패턴을 제공하는 앱을 만들려고 한다.

상현이가 만들 앱의 잠금 패턴은 크기가 2×2부터 $m \times m$까지 다양하고, 인접한 노드끼리만 연결할 수 있다. 인접한 노드란 가로, 세로, 대각선 방향으로 바로 옆에 있는 노드를 말한다. 그래서 네 꼭짓점에 있는 노드는 3개와 연결되고, 나머지 노드는 많으면 8개와 연결된다.

잠금 패턴은 항상 스패닝 트리를 이루어야 한다. 스패닝 트리는 그래프의 간선을 모은 집합으로, 닫힌 루프를 포함하지 않는다. 또 임의의 두 노드 사이에 경로가 있어야 하고, $m^2 = n$개의 정점과 $n-1$개의 간선으로 이루어진다. 잠금 패턴 하나에서 스패닝 트리는 여러 가지가 나올 수 있다.

그래프 $G$의 스패닝 트리 개수를 구하려면 먼저 모든 정점에 $v_1, \dots, v_n$처럼 번호를 붙인다. 그다음 행렬 $T = [t_{ij}]$를 이렇게 만든다.

• $i = j$이면 $t_{ij}$는 $v_i$에 연결된 간선의 개수
• $i \ne j$이면 $v_i$와 $v_j$ 사이에 간선이 있으면 $-1$, 없으면 $0$

스패닝 트리 개수는 $T$의 여인자로 구한다.

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

여기서 $M_{ij}$는 $T$에서 $i$행과 $j$열을 지워 얻은 $(n-1) \times (n-1)$ 행렬의 행렬식이다. $i$와 $j$를 어떻게 골라도 $T$의 여인자는 모두 같은 값이다.

예를 들어 2×2 패턴의 행렬 $T$는 다음과 같다.

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

$i = 1$, $j = 1$로 두고 여인자를 구하면 다음과 같다.

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

따라서 2×2 패턴의 스패닝 트리는 16개다.

3×3 패턴의 행렬 $T$는 다음과 같다.

$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}$

이 행렬의 여인자 값이 3×3 패턴의 스패닝 트리 개수다.

$m \times m$ 패턴에서 만들 수 있는 스패닝 트리의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $N$ ($1 \le N \le 5$)이 주어진다. 다음 $N$개 줄에는 테스트 케이스마다 패턴의 크기 $m$이 한 줄에 하나씩 주어진다. ($2 \le m \le 6$)

각 테스트 케이스마다 $m \times m$ 패턴에서 만들 수 있는 스패닝 트리의 개수를 한 줄에 하나씩 출력한다.

$m = 2$인 패턴은 정점 4개가 서로 모두 연결된 그래프이고, 스패닝 트리는 16가지다.