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$$$)。
输出
对于每个测试用例,输出一个数字 - 最长长凳的最小可能长度。
示例
输入复制
53 4 75 5 51 13 22 4 71 5 4
输出复制
2 1 1 4 2