“暴风城的子民们！让我们在今天团结起来。让我们重申我们的诺言，去维护和保护圣光，我们将共同面对这场黑暗的新风暴，并坚定地抵御它——正如人类过去所做的那样……人类永远都会这样做！”
人群在最后爆发出最热烈的欢呼。一阵阵“瓦里安国王万岁！瓦里安国王万岁！”的呼喊声充满活力与信念，直冲云霄。欢呼声经久不息，回荡在艾尔文森林深处，甚至隐约传到了赤脊山遥远的山峰上。
瓦里安·乌瑞恩在战斗中获得了一块长为 $n$、宽为 $m$ 的矩形金块。现在他想在金块上画一些线，以便之后沿着这些线将金块切割开。
他所画的线必须满足以下要求：
- 线的端点必须位于金块的边界上。
- 线必须至少与金块的一条边界平行。
- 沿着所有线切割后，每一块金块都是长和宽均为整数的矩形。
- 沿着所有线切割后，每一块金块的面积应至少为 $k$。
- 两条线共享的公共点不能超过一个。
瓦里安·乌瑞恩希望以最大化所画线条数量的方式切割金块。
作为联盟的至高王，他当然没有时间做这件事。所以他找到了你！请帮他切割金块！
输入格式
本题包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 每个测试用例包含一行，包含三个整数 $n, m, k$ ($1 \le n, m, k \le 10^5$)。保证 $n \times m \ge k$。
输出格式
对于每个测试用例，输出一行，包含一个整数，表示你可以画出的最大线条数量。
样例
输入 1
2 5 4 2 10 9 13
输出 1
5 4
说明
在第一个测试用例中，瓦里安·乌瑞恩可以画 4 条平行于长为 4 的边界的线，以及 1 条平行于长为 5 的边界的线。沿着这些线切割后，他可以得到 10 块面积为 2 的金块。