Enclosure

A grid is made of $N$ horizontal lines and $M$ vertical lines. The horizontal and vertical lines meet at $N \times M$ intersection points, and each intersection point holds at most one stone.

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

1. A stone is placed on the point.
2. Starting from the point and moving along grid lines, you cannot reach an empty intersection point on the border of the grid by passing through empty intersection points only.

Each move goes along a grid line to a neighbouring intersection point. A path is usable only if its starting point, every point it passes, and its final point are all empty. An empty point on the border is therefore never enclosed.

Place stones so that at least $K$ points are enclosed. Find the minimum number of stones needed.

For example, enclosing 8 points on a $4 \times 5$ grid needs at least 6 stones. The picture below shows one such layout, with the enclosed points marked x.

The first line contains the number of test cases, $T$. Each of the next $T$ lines contains three integers $N$, $M$ and $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 20$

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