Monocarp 有 $$$n$$$ 相同的盒子。每个盒子的重量为$$$m$$$,每个盒子的耐用性为$$$d$$$。
为了节省空间,Monocarp 希望通过将盒子堆叠在一起来构建多个盒子“塔”。每个塔将由正(大于 $$$0$$$)整数个堆叠在一起的盒子组成。为确保箱体不破裂,必须满足以下条件:
- 对于每个盒子, 总计 其上方所有箱子的重量不得超过该箱子的耐久度。
帮助 Monocarp 计算他可以建造的最少塔数,前提是必须使用每个 $$$n$$$ 盒子。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含三个整数 $$$n, m, d$$$ ($$$1 \le n, m, d \le 50$$$)。
输出
对于每个测试用例,打印一个整数 - 塔的最小数量。
示例
输入复制
38 10 208 1 205 3 2
输出复制
315
注意
在第一个示例中,可以建造三座塔,分别由 $$$3$$$、$$$2$$$ 和 $$$3$$$ 盒子组成。
在第二个示例中,所有盒子都足够耐用,可以建造一座由 $$$8$$$ 盒子组成的塔。
在第三个示例中,盒子的重量超出了其耐用性,因此它们无法堆叠在一起。因此,必须建造 $$$5$$$ 单独的塔楼。