Chocolate Bar Problem Statement

You are given a chocolate bar represented as a grid with dimensions N x M. Your task is to cut the chocolate bar, either horizontally or vertically, to obtain exactly 'K' pieces. The cost of each cut is calculated as the square of the break length.

Example:

If you have a chocolate bar with dimensions 3x4, you can:

• Cut horizontally to create two bars of size 1x4 and 2x4, incurring a cost of 4² = 16
• Cut vertically to create two bars of size 3x1 and 3x3, incurring a cost of 3² = 9

Input:

The first line contains an integer 'Q', representing the number of queries. Each subsequent line for each query contains three space-separated integers 'N', 'M', 'K', indicating the dimensions of the chocolate bar and the number of pieces desired, respectively.

Output:

Output 'Q' lines. Each line contains an integer representing the minimum total cost to break the chocolate bar to achieve exactly 'K' pieces for each query.

Constraints:

• 1 <= Q <= 10⁴
• 1 <= N, M <= 30
• 1 <= K <= min(N*M, 50)
• Time Limit: 1 second

Note:

You can disregard any remaining pieces beyond 'K' after the cutting process. The implementation should aim to find and return the minimum cost for obtaining exactly 'K' pieces, without the need for printing, as it is handled by the driver code.