스패닝 트리가 K개인 가장 작은 그래프

무방향 그래프의 스패닝 트리는 그래프의 간선만 사용하면서 모든 정점을 포함하는 트리이고, 간선 수는 정점 수보다 1 작다. 사용한 간선 집합이 다르면 서로 다른 스패닝 트리로 센다.

스패닝 트리가 정확히 $K$ 개인 그래프를 정점을 최대한 적게 써서 만들려고 한다. 단, 아래 과정으로 만든 그래프만 인정한다.

정점이 하나뿐인 그래프에서 시작한다. 이 정점이 중심 $c$ 이면서 끝점 $t$ 이다. 여기에 다음 두 연산을 원하는 순서로 원하는 횟수만큼 적용한다.

옮기기: 중심을 현재 끝점으로 바꾼다. 즉 $c \leftarrow t$ 로 두고, 정점과 간선은 늘지 않는다.
잇기: 양의 정수 $a$ 와 $b$ 를 고른다. $c$ 와 $t$ 가 같은 정점이면 $a + b \ge 3$ 이어야 한다. 새 정점 $x_1, x_2, \ldots, x_{a+b-1}$ 을 만들고 간선 $(t, x_1), (x_1, x_2), \ldots, (x_{a+b-2}, x_{a+b-1}), (x_{a+b-1}, c)$ 를 추가한다. 그 다음 $t \leftarrow x_a$ 로 둔다.

잇기는 끝점에서 출발해 중심으로 돌아오는 새 경로를 붙이고, 그 경로 위의 $a$ 번째 새 정점을 다음 끝점으로 삼는 연산이다. 이 과정으로 만든 그래프에는 자기 자신으로 가는 간선이 없고, 같은 두 정점을 잇는 간선이 두 개 이상 생기지도 않는다.

이 과정으로 만들 수 있으면서 스패닝 트리가 정확히 $K$ 개인 그래프의 최소 정점 수를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에 정수 $K$ 가 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 최소 정점 수이다.

주어진 범위의 모든 $K$ 에 답이 존재하고, 그 값은 항상 22 이하이다.

첫 잇기에서는 $c$ 와 $t$ 가 같은 정점이므로 길이 $a + b$ 인 사이클이 생긴다. 사이클의 스패닝 트리 개수는 간선 수와 같으므로 $a + b$ 개다. $K = 3$ 이면 삼각형 하나로 충분하고 답은 3이다.

$K = 8$ 이면 먼저 $a = 1$ , $b = 2$ 로 삼각형을 만든 뒤, $a = 1$ , $b = 1$ 로 잇기를 한 번 더 적용한다. 정점 4개와 간선 5개짜리 그래프가 되고 스패닝 트리는 8개다.

옮기기를 적용하면 그 뒤에 붙는 부분이 앞서 만든 부분과 정점 하나만 공유한다. 이때 전체 스패닝 트리 개수는 두 부분의 스패닝 트리 개수의 곱이다. 정점 하나를 공유하는 삼각형 두 개는 정점이 5개이고 스패닝 트리가 9개다.