D. 奥林匹克竞赛场地
每个测试点时间限制：1 秒
内存限制：256 兆字节

为了 IT 校园 "NEIMARK" 第一届奥林匹克竞赛的决赛，准备了一个矩形场地。你可以认为场地被分成了 $n$ 行，每行有 $m$ 个供参赛者使用的桌位。总共有 $k$ 名参赛者报名参加了决赛，每位参赛者将坐在一个单独的桌位上。现在，组委会必须为场地中的桌位选择位置。

每个桌位占据一行中的 $m$ 个位置之一。此外，如果多个桌位在同一行中占据连续的位置，我们称这样的一组桌位为一条长凳，组中桌位的数量即为该长凳的长度。例如，在一个 $3 \times 4$ 的场地（$n=3, m=4$）中安排 $7$ 名参赛者，可以如下安排：

（图中第一行有一条长度为 $3$ 的长凳，第二行有一条长度为 $2$ 的长凳，第三行有两条长度为 $1$ 的长凳。）

组委会希望选择位置，使得最长长凳的长度尽可能小。例如，同样的 $7$ 个桌位可以更优地安排，使得所有长凳的长度都不超过 $2$：

（图中每行的桌位被尽可能地分散开。）

给定整数 $n$、$m$ 和 $k$，求出最长长凳的最小可能长度。

输入格式

每个测试文件包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例的描述如下：

每个测试用例只有一行，包含三个正整数 $n$、$m$、$k$（$1 \le n, m, k \le 10^9$，$k \le n \cdot m$）。

输出格式

对于每个测试用例，输出一个整数 —— 最长长凳的最小可能长度。

示例输入

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

示例输出

2
1
1
4
2