CF598E Chocolate Bar

你有一块由 $n \times m$ 个方块组成的矩形巧克力。你想吃恰好 $k$ 个方块，因此可能需要断裂巧克力。 在一次操作中，你可以将任意一块矩形巧克力断裂成两块矩形。你只能沿着方块之间的线条进行断裂：横向或纵向。断裂的费用等于断裂长度的平方。 例如，若你有一块由 $2 \times 3$ 个方块组成的巧克力，你可以横向断裂将其分成两块 $1 \times 3$ 的矩形（断裂费用为 $3^2 = 9$），或通过两种不同的方式纵向断裂，得到两块 $2 \times 1$ 和 $2 \times 2$ 的矩形（断裂费用为 $2^2 = 4$）。 对于给定的多个 $n$、$m$ 和 $k$ 的值，求断裂巧克力的最小总费用。当且仅当断裂操作结束后存在一组矩形碎片，其总方块数恰好为 $k$ 时，你才能吃掉这 $k$ 个方块。剩余的 $n \cdot m - k$ 个方块不必组成一个完整的矩形。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 40910$）——表示需要处理的 $n$、$m$ 和 $k$ 的组数。 接下来的 $t$ 行中，每行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 30$，$1 \leq k \leq \min(n \cdot m, 50)$），分别表示巧克力的尺寸以及你想要吃掉的方块数量。

对于每组 $n$、$m$ 和 $k$，按顺序输出断裂巧克力以使其能吃掉恰好 $k$ 个方块所需的最小总费用。

在第一个示例查询中，需要执行两次断裂： - 将 $2 \times 2$ 的巧克力分成两块 $2 \times 1$（断裂费用为 $2^2 = 4$）， - 将所得的 $2 \times 1$ 分成两块 $1 \times 1$（断裂费用为 $1^2 = 1$）。 在第二个示例查询中，想要吃 $3$ 个方块。可以采用与第一个示例查询相同的策略。 翻译由 QwQ-32B 完成