Bẻ thanh sô cô la

Bạn có một thanh sô cô la hình chữ nhật gồm $n\times m$ ô vuông đơn vị. Bạn muốn ăn đúng $k$ ô vuông, nên có thể phải bẻ thanh sô cô la ra thành nhiều mảnh.

Trong một lần bẻ, bạn chọn một mảnh sô cô la hình chữ nhật bất kỳ và bẻ nó thành hai mảnh hình chữ nhật. Chỉ được bẻ dọc theo các đường thẳng giữa các ô, theo chiều ngang hoặc chiều dọc. Chi phí của một lần bẻ bằng bình phương độ dài đường bẻ.

Ví dụ, với một mảnh $2\times 3$: nếu bẻ ngang thì được hai mảnh $1\times 3$ (chi phí $3^2=9$); nếu bẻ dọc thì được hai mảnh, chẳng hạn $2\times 1$ và $2\times 2$ (chi phí $2^2=4$).

Hãy tìm tổng chi phí nhỏ nhất để sau tất cả các lần bẻ, tồn tại một tập các mảnh hình chữ nhật có tổng diện tích đúng bằng $k$ ô vuông. $k$ ô này là các ô bạn sẽ ăn, chúng không nhất thiết tạo thành một mảnh hình chữ nhật duy nhất. Phần $n·m-k$ ô còn lại cũng không cần tạo thành một hình chữ nhật.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ truy vấn.
• Mỗi dòng trong $t$ dòng tiếp theo chứa ba số nguyên $n$, $m$, $k$.

Dữ liệu ra

Với mỗi bộ $n$, $m$, $k$, in ra trên một dòng chi phí nhỏ nhất cần thiết để có thể ăn đúng $k$ ô sô cô la.

Ràng buộc

• $1\le t\le 40910$
• $1\le n,m\le 30$
• $1\le k\le min(n·m,50)$

Ví dụ