시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 26 19 51.351%

문제

안드로이드는 스마트폰을 잠글때 패턴을 이용한다. 보통 잠근 패턴은 3×3 그리드에 노드 9개로 이루어져 있다. 상현이는 보다 더 높은 보안을 위해 아래와 같은 잠금 패턴을 제공하는 앱을 만드려고 한다.

상현이가 만들 앱의 잠금 패턴의 크기는 2×2부터 m×m까지로 다양하며, 항상 인접한 노드만 연결할 수 있다. 잠금 패턴은 그래프로 나타낼 수 있다. 아래 그림은 2×2, 3×3, 4×4 잠금 패턴을 그래프로 나타낸 것이다. 꼭지점에 해당하는 정점은 총 3개와 연결되어 있고, 나머지 정점은 최대 8개와 연결될 수도 있다. 항상 아래 그림과 같이 인접한 점과만 연결할 수 있다.

잠금 패턴은 항상 스패닝 트리를 이루어야 한다. 스패닝 트리는 그래프 상의 간선의 집합으로, 닫힌 루프를 포함하지 않아야 한다. 또, 임의의 두 점 사이의 경로가 존재해야 하고, 모든 m2 = n개의 정점과 n-1개의 edge로 이루어져 있어야 한다. 잠금 패턴 상에서 스패닝 트리는 여러 가지 경우가 나올 수 있다.

그래프 G의 스패닝 트리의 개수를 구하기 위해 모든 정점에 번호 v1, ..., vn을 붙인다. 이제 행렬 T = [tij]를 아래와 같이 만들 수 있다.

  • i = j인 경우에는 vi와 연결된 간선의 개수
  • i ≠ j인 경우에 vi와 vj 사이에 간선이 있으면 -1, 없으면 0

스패닝 트리의 개수는 다음과 같이 구할 수 있다.

cofactor of aij = (-1)i+jMij 

여기서 Mij는 T에서 i행과 j열을 지워서 얻은 (n-1) × (n-1) 행렬의 행렬식(determinant)이다. T의 모든 cofactor는 같은 결과를 갖는다.

예를 들어, 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로 두고 cofator를 구해보면 아래와 같다.

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

따라서, 스패닝 트리의 개수는 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}\]

T의 모든 cofactor는 같은 결과를 갖고, 이 답이 스패닝 트리의 개수가 된다.

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

입력

첫째 줄에 테스트 케이스의 개수 N (1 ≤ N ≤ 5)가 주어진다. 다음 N개 줄에는 테스트케이스 한 줄에 하나씩 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 패턴의 크기 m이 주어진다. (2 ≤ m ≤ 6)

출력

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

예제 입력

1
2

예제 출력

16

힌트

m = 2인 경우 아래와 같이 16가지 경우가 있다.