This is an extension to the problem DEFKIN http://www.spoj.com/problems/DEFKIN/ and solve it first before doing this.

Theodore implements a new strategy game “Defense of a Kingdom”. On each level a player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column.

Now the king inputs width(w),height(h),number of towers(n). Here n <= min(w, h).

There there can be many ways to place the towers in the grid.

Lets define a function penalty(N_i) for the ith combination of tower placements, which is number of cells in the largest undefended rectangle. For example, one of the combinations of placing a tower is shown in the picture and has a penalty=12.

Suppose there are in total k combinations. Then there are penalty(N₁), penalty(N₂), penalty(N₃) ... penalty(N_k).

The task of the user is to find the minimum of these penalties.

Input

The first line of the input file contains the number of test cases.

Each test case consists of a line with three integer numbers: w — width of the grid, h — height of the grid and n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).

Output

For each test case, output a single integer number- the minimum penalty. Output answer for each test case in a new line.

Example

Input:
1
15 8 3

Output:
6