题目描述

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

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

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

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

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

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

输入格式

本题有多组数据

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

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

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