[E] Barra de Chocolate

Enlace a Codeforces

Tienes una barra rectangular de chocolate que consiste de $n \times m$ cuadrados. Quieres comer exactamente $k$ cuadrados, así que puede que necesites partir la barra de chocolate.

En un movimiento puedes partir un trozo rectangular de chocolate en otros dos trozos rectangulares siguiendo únicamente las líneas verticales y horizontales entre los cuadrados. Adicionalmente, cada partición tiene un costo equivalente al cuadrado de su longitud.

Por ejemplo, si tienes una barra de chocolate de $2 \times 3$ unidades, podrías romperla horizontalmente y obtener dos trozos de $1 \times 3$ (con un costo de $3^2 = 9$), o romperla verticalmente de dos formas, y obtener dos trozos de $2 \times 1$ y $2 times 2$ unidades respectivamente (siendo aquí el costo igual a $2^2 = 4$).

Para varios valores de $n$, $m$ y $k$ encuentra el menor costo posible en particiones. Puedes comer exactamente $k$ cuadrados sólo cuando haya un conjunto de trozos de chocolate con un tamaño total igual a $k$ cuadrados. Los $n\cdot m - k$ cuadrado restantes no necesariamente tienen que formar un único trozo rectangular.

Entrada

La primera línea de la entrada contiene un único entero $t$ ($1 \leq 1 \leq 40910$) - la cantidad de valores $n$, $m$, y $k$ a procesar.

Cada una de las siguientes $t$ líneas contiene tres enteros $n$, $m$ y $k$ ($1 \leq n, m \leq 30$, $1 \leq k \leq min(n\cdot m, 50)$) - las dimensiones de la barra de chocolate y el número de cuadrados que quieres comer respectivamente.

Salida

Para cada uno de los casos imprime el menor costo total necesario para partir la barra de chocolate con el fin de comer exactamente $k$ cuadrados.

Ejemplos

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

output:
5
5
4
0

Nota

En el primer caso del ejemplo se necesitan dos particiones:

• dividir la barra de $2 \times 2$ en dos trozos de $2 \times 1$ (con un costo de $2^2 = 4$)
• dividir una de los trozos de $2 \times 1$ resultantes en dos trozos de $1 \times 1$ (con un costo de $1^2 = 1$)

En el segundo caso, como son 3 los cuadrados que uno quiere comer, se puede usar exactamente la misma estrategia del caso anterior.