该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

首届 IT Campus "NEIMARK" 奥林匹克的决赛场地被布置为一个矩形区域。你可以认为该场地被划分为 $n$ 行，每行包含 $m$ 个参赛者座位的点位。共有 $k$ 名参赛者注册了决赛，每位参赛者将坐在单独的座位上。现在，组委会需要为这些座位选择具体位置。

每个座位占据某一行中的 $m$ 个点位之一。此外，若同一行中多个连续的座位被占据，我们称这样的座位组为一个长凳，组内座位的数量称为长凳的长度。例如，在 $3 \times 4$ 的场地（$n = 3$, $m = 4$）中安排 $7$ 名参赛者的座位可能如下所示：

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

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

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

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 10^4$)。接下来是每个测试用例的描述。

每个测试用例单独一行，包含三个正整数 $n$、$m$、$k$ ($1 \leq n, m, k \leq 10^9$, $k \leq n \cdot m$)。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

2
1
1
4
2