cut-the-rectangle

A rectangle sheetof NxM. Make C cuts parallel to edges such that area of the smallest piece after cutting is maximised i.e. After cutting, the area of the smallest rectangle should be maximised. Print the area of the smallest such rectangle.
All cuts should be made at integer points.
If it is not possible to make c cuts, print -1.

Input
First line : number of test cases
A single line contains three integers n, m, c (T ≤ 1000  1 ≤ N, M≤ 10 ^ 9;  1 ≤ C ≤ 10 ^ 9).

Output
Output a single integer representing the answer. If it is impossible to cut the rectangle c times, print -1.

Explanation of Sample Input :

If you have a rectangle of size 3X4, and you can make only 1 cut. Then cut it into two rectangles of 3X2 and 3X2 to get the maximum area of smallest rectangle i.e. 6.
Supposedly, If you cut it into 3X1 and 3X3, then the smallest area would be 3 , which is less than 6.
So the maximum area of minimum rectangle will be 6 ( 3X2 rectangle).

Problem Setter : Shivam Beri

SAMPLE INPUT
1
3 4 1

SAMPLE OUTPUT
6

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: