둘러싸기

이 문제에서는 $N \times M$ 직사각형 격자(N개의 수평선분과 M개의 수직선분)에서 적어도 K개의 교점을 둘러싸기 위해 놓아야 하는 돌의 최소 개수를 구해야 한다. 다음 조건 중 하나라도 참이면 교점이 둘러싸였다고 한다.

• 그 점에 돌이 놓여 있다.

• 그 점에서 출발하여 빈 교점만을 지나 격자선을 따라 격자 경계에 있는 빈 점까지 가는 경로를 그릴 수 없다.

예를 들어 4x5 격자에서 8개의 점을 둘러싸려면 적어도 6개의 돌이 필요하다. 가능한 여러 돌 배치 중 하나가 아래에 나와 있다. 둘러싸인 점은 "x"로 표시되어 있다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ N. 1 ≤ M. 1 ≤ K ≤ N × M.

작은 데이터 세트

시간 제한: 60초. N × M ≤ 20.

큰 데이터 세트

시간 제한: 120초. N × M ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 테스트 케이스는 세 정수 N M K가 있는 한 줄로 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 필요한 돌의 최소 개수이다.