题目描述

给定一个 $n\times m$ 的矩形场地，需要放置 $k$ 张桌子。在同一行中，相邻的桌子构成一个“长凳”，其长度等于连续桌子的数量。请你安排桌子，使得所有长凳中最长的长度尽可能小，并求出这个最小的最大长凳长度。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来每个测试用例占一行，包含三个正整数 $n, m, k$。

$1 \le n, m, k \le 10^9$，且保证 $n \times m \ge k$。

输出格式

对于每个测试用例，输出一个整数，表示最优安排下最长长凳的最小可能长度。

样例输入

5
3 4 7
5 5 5
1 13 2
2 4 7
1 5 4

样例输出

2
1
1
4
2

说明

例如，在 $3\times 4 (n=3,m=4)$的场地上安排 $7$ 个桌子的最优方法如下:

此时所有长凳的长度不超过 $2$