시끄러운 이웃

당신은 $R \times C$ 격자 모양으로 아파트가 놓인 건물의 주인이다. 아파트 한 채는 벽 네 개로 둘러싸인 단위 정사각형이다. 이 중 $N$채를 한 채당 한 명씩 세입자에게 임대하고 나머지는 비워 둔다.

세입자는 모두 시끄럽다. 사람이 사는 두 아파트가 벽 하나를 맞대고 있으면 건물의 불쾌도가 1 늘어난다. 꼭짓점만 맞닿은 두 아파트는 벽을 맞댄 것으로 세지 않는다. 예를 들어 $2 \times 2$ 건물에 네 채가 모두 차 있으면 이웃끼리 맞댄 벽이 네 개이므로 불쾌도는 4다.

$N$명을 불쾌도가 가장 작아지도록 배치하고, 그 최솟값을 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에 각각 세 정수 $R$, $C$, $N$이 공백 하나로 구분되어 주어진다.

제한

• $1 \le T \le 1000$
• $1 \le R \times C \le 16$
• $0 \le N \le R \times C$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 건물의 불쾌도 최솟값이다.

예제의 첫 번째 케이스는 $2 \times 3$ 건물을 빈틈없이 채우므로 내부 벽 일곱 개가 모두 두 세입자 사이에 놓인다.

두 번째 케이스에서는 $4 \times 1$ 건물에 세입자 두 명을 벽을 맞대지 않게 넣는 방법이 여럿 있다.

세 번째 케이스에서는 여덟 명을 $3 \times 3$ 건물의 가장자리를 따라 고리 모양으로 놓고 가운데를 비우는 것이 최선이다.

아래 그림은 예제의 1번, 2번, 3번 케이스를 나타낸다. 빨간 벽 하나가 불쾌도 1에 해당한다.