Tổng chữ nhật

Cụi vẽ một bảng gồm \(m\) dòng và \(n\) cột, sau đó điền các số nguyên tăng dần bắt đầu từ \(0\) theo thứ tự từ trái sang phải, từ trên xuống dưới.
Do đó ô ở dòng \(r\) và cột \(c\) (đánh số từ \(0\)) có giá trị:
$
a_{r,c} = r\cdot n + c.
$

| \(0\) | \(1\) | \(2\) | \(3\) |
|—|—|—|—|
| \(4\) | \(5\) | \(6\) | \(7\) |
| \(8\) | \(9\) | \(10\) | \(11\) |

Lấy ví dụ với \(m=4, n=3\).

Với một số nguyên \(S\) cho trước, hãy tìm một hình chữ nhật con (các cạnh song song với cạnh của bảng) sao cho:

• Tổng các số trong hình chữ nhật đó đúng bằng \(S\).
• Diện tích của hình chữ nhật là nhỏ nhất có thể.

Diện tích của một hình chữ nhật có \(h\) dòng và \(w\) cột bằng \(h\cdot w\).

Nếu không tồn tại hình chữ nhật thỏa mãn, hãy in ra \(-1\).

Input

• Dòng đầu chứa số nguyên dương \(t\) \((1 \le t \le 3)\) là số lượng test.
• Mỗi test gồm một dòng chứa ba số nguyên \(m, n, S\) \((1 \le m, n \le 10^9,\ 0 \le S \le 10^{12})\).

Output

• Với mỗi test, in ra một số nguyên là diện tích nhỏ nhất của hình chữ nhật có tổng đúng bằng \(S\). Nếu không có, in ra \(-1\).

Input

%
2
3 4 34
1 1 1

Output

%
4
-1