돌로 가두기

가로선 $N$개와 세로선 $M$개로 이루어진 격자가 있다. 가로선과 세로선이 만나는 교차점은 모두 $N \times M$개이고, 각 교차점에는 돌을 하나까지 놓을 수 있다.

교차점 하나가 다음 두 조건 중 하나를 만족하면 그 점은 갇힌 점이다.

1. 그 점에 돌이 놓여 있다.
2. 그 점에서 출발해 격자선을 따라 이동할 때, 빈 교차점만 지나서는 격자 경계의 빈 교차점에 도달할 수 없다.

이동은 격자선을 따라 이웃한 교차점으로 한 칸씩만 한다. 출발점, 지나는 점, 도착점이 모두 비어 있어야 그 경로를 쓸 수 있다. 따라서 경계 위에 있는 빈 교차점은 갇힌 점이 아니다.

갇힌 점이 $K$개 이상이 되도록 돌을 놓으려고 한다. 필요한 돌의 최소 개수를 구하라.

예를 들어 $4 \times 5$ 격자에서 점 8개를 가두려면 돌이 적어도 6개 필요하다. 아래 그림은 그런 배치 중 하나이고, 갇힌 점을 x로 표시했다.

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

제한

• $1 \le T \le 100$
• $1 \le N$
• $1 \le M$
• $1 \le K \le N \times M$
• $N \times M \le 20$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 필요한 돌의 최소 개수이다.