돌로 교점 가두기

가로선 $N$개와 세로선 $M$개로 이루어진 격자가 있다. 가로선과 세로선이 만나는 교점은 모두 $N \times M$개다. 이 교점 중 몇 곳에 돌을 놓아 교점 $K$개 이상을 가두려고 한다.

교점 하나는 다음 두 조건 중 하나를 만족하면 가둔 것이다.

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 1000$

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