Enclosing Grid Points

A grid has $N$ horizontal lines and $M$ vertical lines, so it has $N \times M$ intersection points. You put stones on some of the intersection points, and you want at least $K$ points to end up enclosed.

An intersection point is enclosed if either of the following holds.

1. A stone sits on the point.
2. Starting from the point, moving along the grid lines to neighboring points and stepping only on points that hold no stone, you cannot reach an empty point on the border of the grid.

Find the smallest number of stones that leaves at least $K$ enclosed points.

For example, enclosing 8 points on a $4 \times 5$ grid takes at least 6 stones. The picture below shows one such placement. Enclosed points are marked with an x.

The first line of the input gives the number of test cases, $T$. Each of the next $T$ lines holds three integers $N$, $M$, $K$ separated by spaces.

Limits

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

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the minimum number of stones.