Stormwind

$\space \space$*"So, people of Stormwind! Let us unite this day. Let us renew our promise to uphold and protect the Light, and together we will face down this dark new storm and stand firm against it—as humanity always has… and humanity always will!"*

$\space \space$*The crowd saved its greatest roars for the end. A chorus of "Long live King Varian! Long live King Varian!" rose into the sky with vigor and conviction. The cheers were unending, echoing deep into Elwynn Forest and faintly reaching even the distant peaks of the Redridge Mountains.*

Varian Wrynn gained a rectangular piece of gold in the battle, with length $n$ and width $m$. Now he wants to draw some lines on the gold, so that later he can cut the gold along the lines.

The lines he draws should satisfy the following requirements:

1. The endpoints of the lines should be on the boundary of the gold.
2. The lines should be parallel to at least one boundary of the gold.
3. After cutting along all the lines, each piece of gold is a rectangle with integer length and width.
4. After cutting along all the lines, the area of each piece of gold should be at least $k$.
5. Two lines should not share more than one common points.

Varian Wrynn wants to cut the gold in such a way that maximizes the lines he draws.

As Alliance's Supreme King, he certainly doesn't have time to do this. So he finds you! Please help him to cut the gold!

The input consists of multiple test cases.

The first line contains an integer $T\ (1\leq T \leq 100)$ indicating the number of test cases.

Each test case consists of one line containing three integers $n, m, k\ (1\leq n,m,k \leq 10^5)$. Its guaranteed that $n\times m \geq k$.

For each test case, output one line containing one integer, the maximum number of lines you can draw.

2
5 4 2
10 9 13

5
4

In the first test case, Varian Wrynn can draw 4 lines parallel to the boundary of length 4 and 1 line parrallel to the boundary of length 5. After cutting along the lines, he can get 10 pieces of gold of size 2.

2022“杭电杯”中国大学生算法设计超级联赛（8）