← 返回题目列表

Codeforces · 2091/D

D. 奥林匹克竞赛地点

中文机器翻译题面 查看原题

IT校园“NEIMARK”首届奥林匹克竞赛的决赛,准备了一个长方形的场地。您可以假设场地分为 $$$n$$$ 行,每行包含 $$$m$$$ 参与者办公桌位。共有 $$$k$$$ 名参赛者报名参加决赛,每位参赛者将坐在单独的桌子上。现在,组委会必须选择场馆内的办公桌位置。

每张桌子占据一排 $$$m$$$ 个位置之一。此外,如果几张桌子在同一排占据连续的位置,我们称这样的一组桌子为 长凳,组中桌子的数量就是长凳的长度。例如,在 $$$3 \times 4$$$ 场地上容纳 $$$7$$$ 参与者($$$n = 3,m = 4$$$)可以安排如下:

在上图中,第一行有一个长度为$$$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$$$)。

输出

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

示例

输入
复制

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

输出
复制

2
1
1
4
2