您盯着电脑屏幕的时间太长了;是时候让它休息一下,去摸一些草了。
您的屏幕是一条长度为 $$$a$$$ 的线,上面显示了 $$$n$$$ 选项卡。您想要通过单击右端点处的 x 来关闭所有选项卡。
每个制表符都是长度为 $$$\textrm{len}=\min(b,\frac{a}{m})$$$ 的段,其中 $$$m$$$ 是剩余制表符的数量。选项卡始终从屏幕左端点开始按顺序紧密排列;也就是说,x 距离左端点 $$$\textrm{len},2\cdot \textrm{len},3\cdot \textrm{len},\ldots,m\cdot\textrm{len}$$$ 个单位。请注意,当您关闭选项卡时,每个选项卡的长度都会发生变化。
现在您的光标位于屏幕的左端点。你想知道最少的数量是多少 次 您需要移动鼠标来关闭所有选项卡。
如果您难以理解该声明,您还可以参考浏览器选项卡进行可视化,或单击此处。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例都是一行三个整数 $$$a$$$、$$$b$$$ 和 $$$n$$$ ($$$1\le b\le a \le 10^9$$$、$$$1\le n \le 10^9$$$)。
输出
对于每个测试用例,输出一个整数 - 关闭所有选项卡所需移动鼠标的最少次数。
示例
输入复制
128 1 69 6 210 3 110 1 109 2 15 5 66 2 79 1 93 2 68 1 78 1 98 2 4
输出复制
121111212121
注意
在第一个测试用例中,可能的操作是将光标移动到 $$$1$$$ 并按 $$$6$$$ 次。
在第二个测试用例中,可能的操作过程是将光标移动到 $$$4.5$$$ 并按一次,然后将其移动到 $$$6$$$ 并再次按。可以证明,少于 $$$2$$$ 的移动无法关闭选项卡。