Minh has a box of pencils. The box is a rectangle of size M x—N, where position (i, j) has a pencil  with a length of exactly i x 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^6, 1 <= L <= 10^12) 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