【cfgym100541】Pencil Game

2015年3月14日9850

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 ≤ 106, 1 ≤ L ≤ 1012) 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.

Sample test(s)
input

output

题解

我是傻逼T T

如果确定了矩形的长宽,就比较容易判是否可行

然后考虑枚举面积K

K一定是2L的约数,且K不会超过根号L级别

然后再枚举一条边,同样只要根号K

我是傻逼T T