Noisy Neighbors (Large)

You are the landlord of an apartment building laid out as an $R$ by $C$ grid. Each apartment is one unit square cell with four walls. You want to rent $N$ of these apartments, one tenant per apartment, and leave the rest empty.

The trouble is that every prospective tenant is noisy. Whenever two occupied apartments share a wall, the building gains one point of unhappiness. Two apartments that meet only at a corner share no wall, so they add nothing. For example, a $2 \times 2$ building with all four apartments occupied has four walls between neighbours, so its unhappiness is 4.

Place the $N$ tenants as well as possible and report the minimum unhappiness of the building.

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

Limits

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

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 possible unhappiness of that building.

A $2 \times 3$ building with six tenants has all seven internal walls sitting between neighbours.

A $4 \times 1$ building with two tenants has several placements in which no wall is shared.

A $3 \times 3$ building with eight tenants is best filled as a ring around the empty centre cell.