Bạn có một thanh sô-cô-la hình chữ nhật chứa ~n \times m~ ô vuông. Bạn muốn ăn chính xác ~k~ ô sô-cô-la, vì vậy bạn phải tìm cách bẻ thanh sô-cô-la này ra.

Trong một thao tác, bạn có thể chọn và bẻ một thanh sô-cô-la hình chữ nhật thành hai thanh hình chữ nhật nhỏ hơn. Bạn chỉ có thể bẻ theo các đường thẳng giữa các ô vuông: theo chiều dọc hoặc theo chiều ngang. Chi phí cho thao tác sẽ bằng bình phương độ dài cần bẻ.

Ví dụ, nếu bạn có một thanh sô-cô-la chứa ~2 \times 3~ ô vuông, thì bạn có thể bẻ theo chiều ngang và được hai thanh ~1 \times 3~ (chi phí cho thao tác này là ~3^2 = 9~), hoặc bạn có thể bẻ theo chiều dọc ở một trong hai vị trí và được hai thanh: ~2 \times 1~ và ~2 \times 2~ (chi phí cho thao tác này là ~2^2 = 4~).

Cho các giá trị ~n, m, k~, hãy tìm tổng chi phí nhỏ nhất để bẻ thanh sô-cô-la. Bạn có thể ăn đúng ~k~ ô sô-cô-la nếu sau khi thực hiện các thao tác bẻ, tồn tại một tập hợp các thanh sô-cô-la hình chữ nhật mà chứa tổng cộng ~k~ ô vuông. Ngoài ra, ~nm-k~ ô vuông còn lại không nhất thiết phải thuộc cùng một thanh hình chữ nhật.

Input

Dòng đầu tiên chứa một số nguyên ~t~ ~(1 \leq t \leq 40910)~ - số lượng bộ dữ liệu cần xử lí.

Mỗi dòng trong ~t~ dòng tiếp theo chứa ba số nguyên ~n, m, k~ ~(1 \leq n, m \leq 30, 1 \leq k \leq min(nm, 50))~ - lần lượt là kích thước của thanh sô-cô-la và số ô vuông sô-cô-la mà bạn muốn ăn.

Output

Với mỗi bộ dữ liệu, in ra chi phí nhỏ nhất cho việc bẻ thanh sô-cô-la để ăn được chính xác ~k~ ô vuông.

Sample Input

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

Sample Output

5
5
4
0

Note

Ở truy vấn đầu tiên, ta có thể thực hiện hai thao tác bẻ:

• Bẻ thanh ~2 \times 2~ thành hai thanh ~2 \times 1~ (chi phí ~2^2 = 4~),
• Bẻ một thanh ~2 \times 1~ vừa nhận được, thành hai thanh ~1 \times 1~ (chi phí ~1^2 = 1~).

Ở truy vấn thứ hai, để ăn ~3~ ô thì ta cũng có thể thực hiện thao tác tương tự như truy vấn đầu tiên.