← 返回题目列表

Codeforces · 598/E

E. 巧克力棒

中文机器翻译题面 查看原题

您有一个由 n × m 个单个方块组成的矩形巧克力棒。你想吃恰好 k 块,所以你可能需要打破巧克力棒。

只需一步,您就可以将任意一块矩形巧克力分成两块。您只能通过方块之间的线来断开:水平或垂直。断裂成本等于断裂长度的平方。

例如,如果您有一个由 2 × 3 单位方块组成的巧克力棒,那么您可以水平地打破它并获得两个 1 × 3 块(这种打破的成本为 32 = 9),或者您可以以两种方式垂直地打破它并获得两块:2 × 1 和 2 × 2(这种打破的成本为 22 = 4)。

对于几个给定值 n、m 和 k,找出破坏的最小总成本。如果在所有的打碎操作之后,有一组总大小等于 k ​​个方格的矩形巧克力块,那么您可以恰好吃掉 k 个方格的巧克力。剩余的n·m-k个正方形不一定形成单个矩形块。

输入

输入的第一行包含一个整数 t (1 ≤ t ≤ 40910) — 要处理的值 n、m 和 k 的数量。

接下来的 t 行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ min(n·m, 50))——分别是巧克力棒的尺寸和你想吃的方块的数量。

输出

对于每个 n、m 和 k,打印打碎巧克力棒所需的最小总成本,以便能够恰好吃掉 k 块巧克力。

示例

输入 #1

4
2 2 1
2 2 3
2 2 2
2 2 4

输出 #1

5
5
4
0

注意

在示例的第一个查询中,需要执行两次中断:

- 将 2 × 2 条分成两块 2 × 1(成本为 22 = 4),
- 将生成的 2 × 1 分成两个 1 × 1 块(成本为 12 = 1)。

在样本的第二个查询中,一个人想吃 3 个单位方块。可以使用与示例的第一个查询完全相同的策略。