Minh has a box of pencils. The box is a rectangle of size M × N, where position (i, j) has a pencil  with a length of exactly i × N + j (0 ≤ i ≤ M-1, 0 ≤ j ≤ N-1). Note that position (0, 0) does not have any pencil hence having a length of 0.

He wonders if he could select a sub-rectangle of the box and join all the pencils within that sub-rectangle together, to get a new long pencil that has a specific length L that he wants.

Your task is to find a sub-rectangle of the box in which the total length of the contained pencils is L and return the area of that the sub-rectangle. If there are multiple solutions, return the smallest possible area. If there's no such sub-rectangle, return -1.

Input

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 150. The following lines describe the datasets.

Each dataset contains three space-separated numbers M, N and L (1 ≤ M, N ≤ 10⁶, 1 ≤ L ≤ 10¹²) written in one line.

Output

For each dataset, write in one line the smallest possible area of the sub-rectangle in which the total sum of pencil lengths is L. Write in one line -1 if there is no such sub-rectangle.

Example

Input:
2
2 3 8
2 2 7

Output:
4
-1