SP23185 VNACM14H - 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. Minh has a box of pencils. The box is a rectangle of size M Ă—N, where position (i, j) has a pencilÂ

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.

  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.