CF598E.Chocolate Bar

You have a rectangular chocolate bar consisting of n × m single squares. You want to eat exactly k squares, so you may need to break the chocolate bar.

In one move you can break any single rectangular piece of chocolate in two rectangular pieces. You can break only by lines between squares: horizontally or vertically. The cost of breaking is equal to square of the break length.

For example, if you have a chocolate bar consisting of 2 × 3 unit squares then you can break it horizontally and get two 1 × 3 pieces (the cost of such breaking is 32 = 9), or you can break it vertically in two ways and get two pieces: 2 × 1 and 2 × 2 (the cost of such breaking is 22 = 4).

For several given values n, m and k find the minimum total cost of breaking. You can eat exactly k squares of chocolate if after all operations of breaking there is a set of rectangular pieces of chocolate with the total size equal to k squares. The remaining n·m - k squares are not necessarily form a single rectangular piece.

你有一块 $n \times m$ 的矩形巧克力，由 $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$ 个方格不一定构成一块完整的矩形。

The first line of the input contains a single integer t (1 ≤ t ≤ 40910) — the number of values n, m and k to process.

Each of the next t lines contains three integers n, m and k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ min(n·m, 50)) — the dimensions of the chocolate bar and the number of squares you want to eat respectively.

输入的第一行包含一个整数 $t$（$1 ≤ t ≤ 40910$）—— 表示需要处理的 $(n, m, k)$ 三元组的个数。

接下来的 $t$ 行，每行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 30$，$1 ≤ k ≤ \min(n·m, 50)$）—— 分别表示巧克力棒的尺寸以及你想要吃掉的方格数量。

For each n, m and k print the minimum total cost needed to break the chocolate bar, in order to make it possible to eat exactly k squares.

对于每组 $n$、$m$ 和 $k$，输出将该巧克力块掰开以恰好吃掉 $k$ 个方格所需的最小总代价。

In the first query of the sample one needs to perform two breaks:

• to split 2 × 2 bar into two pieces of 2 × 1 (cost is 22 = 4),
• to split the resulting 2 × 1 into two 1 × 1 pieces (cost is 12 = 1).

In the second query of the sample one wants to eat 3 unit squares. One can use exactly the same strategy as in the first query of the sample.

在样例的第一个查询中，需要进行两次切割：

• 将 $2 \times 2$ 的巧克力条切分为两块 $2 \times 1$（花费为 $2^2 = 4$），
• 将得到的 $2 \times 1$ 巧克力条再切分为两块 $1 \times 1$（花费为 $1^2 = 1$）。

在样例的第二个查询中，目标是吃掉 $3$ 个单位正方形。可以采用与样例第一个查询完全相同的策略。