시끄러운 이웃 (라지)

당신은 $R$행 $C$열 격자 모양으로 지어진 아파트 건물의 집주인이다. 각 세대는 벽 네 개로 둘러싸인 단위 정사각형 칸 하나이다. 이 중 $N$개의 세대에 세입자를 한 명씩 들이고 나머지는 비워 둔다.

문제는 세입자가 모두 시끄럽다는 점이다. 사람이 사는 두 세대가 벽 하나를 맞대고 있으면 건물의 불쾌도가 1 올라간다. 모서리만 맞닿은 두 세대는 벽을 공유하지 않으므로 불쾌도가 오르지 않는다. 예를 들어 $2 \times 2$ 건물의 네 세대가 모두 차 있으면 이웃끼리 맞댄 벽이 네 개이므로 이 건물의 불쾌도는 4이다.

세입자 $N$명을 가장 좋게 배치했을 때 건물의 최소 불쾌도를 구하여라.

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

제한

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

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

$2 \times 3$ 건물에 여섯 명이 들어가면 내부 벽 일곱 개가 전부 이웃 사이에 놓인다.

$4 \times 1$ 건물에 두 명을 넣을 때는 서로 벽을 맞대지 않는 배치가 여러 가지 있다.

$3 \times 3$ 건물에 여덟 명을 넣을 때는 가운데 한 칸을 비우고 나머지를 고리 모양으로 채우는 것이 최선이다.