401849: GYM100541 H Pencil Game

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.

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.

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.

4
2 3 8
3 3 10
3 3 36
1000000 1000000 1000000000000

4
-1
9
2