시끄러운 이웃

당신은 아파트들이 R x C 격자를 이루는 건물을 소유한 임대인이다. 각 아파트는 네 개의 벽을 가진 단위 정사각형 칸이다. 이 아파트들 중 N개를 아파트마다 정확히 한 명씩 세입자에게 임대하고, 나머지는 비워 두려고 한다. 안타깝게도 입주할 가능성이 있는 세입자들은 모두 시끄럽기 때문에, 입주한 두 아파트가 벽을 공유할 때마다(모서리만 공유하는 경우는 제외한다) 건물의 불행도가 한 점 증가한다. 예를 들어, 모든 아파트에 세입자가 입주한 2x2 건물에서는 이웃한 세입자들이 공유하는 벽이 네 개이므로, 건물의 불행도 점수는 4이다.

N명의 세입자를 최적으로 배치할 때, 건물의 최소 불행도는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 1000. 0 ≤ N ≤ R*C.

작은 데이터 세트

시간 제한: 240초. 1 ≤ R*C ≤ 16.

큰 데이터 세트

시간 제한: 480초. 1 ≤ R*C ≤ 10000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 공백으로 구분된 세 정수 R, C, N이 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 가능한 건물의 최소 불행도이다.

케이스 #1에서는 모든 방에 세입자가 입주해 있으며, 내부 벽 일곱 개 모두의 양쪽에 세입자가 있다.

케이스 #2에서는 두 세입자가 벽을 공유하지 않도록 배치하는 방법이 여러 가지 있다. 그중 하나가 아래에 나와 있다.

케이스 #3에서 최적의 전략은 가운데 아파트를 비워 두고 여덟 명의 세입자를 고리 모양으로 배치하는 것이다.

다음은 예제 케이스 1-3의 그림이다. 빨간색 벽 하나마다 불행도가 한 점 증가한다.