스패닝 트리가 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$가 한 줄에 하나씩 주어진다.

• $1 \le T \le 300$
• $3 \le K \le 10000$

각 테스트 케이스마다 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개다.