Noisy Neighbors

You are a landlord. Your building is an $R \times C$ grid of apartments, and each apartment is a unit square with four walls. You want to rent out $N$ of the apartments to tenants, exactly one tenant per apartment, and leave the rest empty.

Every tenant is noisy. Whenever two occupied apartments share a wall, the building gains one point of unhappiness. Two apartments that touch only at a corner do not share a wall. For example, a $2 \times 2$ building with all four apartments occupied has four walls between neighboring tenants, so its unhappiness is 4.

Place the $N$ tenants so that the unhappiness is as small as possible, and report that minimum.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $R$, $C$, and $N$, separated by single spaces.

Limits

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

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting at 1 and $y$ is the minimum possible unhappiness of the building.

In sample case 1, every apartment of the $2 \times 3$ building is occupied, so all seven internal walls sit between two tenants.

In sample case 2, the two tenants fit into the $4 \times 1$ building in several ways without sharing a wall.

In sample case 3, the best placement puts the eight tenants in a ring along the border of the $3 \times 3$ building and leaves the middle apartment empty.

The picture below shows sample cases 1, 2, and 3. Each red wall costs one point of unhappiness.