题目描述

贝尔周赛的场地被布置为一个矩形区域。你可以认为该场地被划分为 $n$ 行，每行包含 $m$ 个参赛者座位的点位。

共有 $k$ 名参赛者注册了决赛，每位参赛者将坐在单独的座位上。现在，组委会需要为这些座位选择具体位置。

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

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

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

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

输入格式

本题有多组数据

第一行输入一个整数 $t$ 代表测试数据组数。

• 每一组数据第一行行输入三个整数 $n,m,k$。

输出格式

对于每一组数据，输出一个数字。代表最长长凳的最小可能长度。

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

2
1
1
4
2

提示

数据范围

对于 $100\%$ 的数据，$1\leq t\leq 10^5$，$1 \leq n, m, k \leq 10^9$, $k \leq n \cdot m$。

• 子任务 $1$（$30$ 分）：$k\leq 100$。
• 子任务 $2$（$70$ 分）：没有特殊限制。