https://codeforces.com/problemset/problem/598/E

题意：

有一块长方形的巧克力，可以分成n*m小块。如果吃k小块巧克力，因此需要掰开这块巧克力。

在每一次操作中可以把任意一块矩形形状的巧克力掰成两块矩形形状的巧克力。

只能沿着巧克力小块之间的分割线掰开巧克力——可以沿着水平方向或是竖直方向掰开。

掰开巧克力的花费等于分割线长度的平方。

例如，如果有一块2*3的巧克力，那么可以沿着水平方向掰从而得到两块1*3的巧克力，这次操作的花费为3^2=9。

或者也可以沿着竖直方向掰从而得到一块2*1的巧克力和一块2*2的巧克力，这次操作的花费为2^2=4。

对于每一个给出的n，m和k，计算出最小花费。你可以用多块巧克力凑出k小块巧克力。

剩余的巧克力可以不是完整的一块。

输入格式：

输入数据的第一行包括1个整数t(1<=t<=40910)，表示数据组数。

接下来的t行每一行都包含3个整数n，m和k(1<=n,m<=30,1<=k<=min(n*m,50))，其意义见上文。

 题解：

状态值f[i][j][k]表示i*j的巧克力得到k个小巧克力的最小花费