您有一个由 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 个单位方块。可以使用与示例的第一个查询完全相同的策略。