Monocarp 正在玩 MMORPG。该MMORPG中有两种常用的货币——金币和银币。 Monocarp 想为他的角色购买一把新武器,而该武器需要 $$$n$$$ 银币。不幸的是,目前 Monocarp 根本没有硬币。
Monocarp可以通过完成游戏中的任务来赚取金币。每个任务都会产生一枚金币。 Monocarp 还可以通过游戏内交易系统交换硬币。 Monocarp 花了几天时间分析游戏内的经济;他得出以下结论:可以用$$$a$$$银币出售一枚金币(即Monocarp可以损失一枚金币以获得$$$a$$$银币),或者以$$$b$$$银币购买一枚金币(即Monocarp可以损失$$$b$$$银币以获得一枚金币)。
现在,Monocarp 想要计算他必须完成的最小任务数量,以便在滥用游戏内经济后至少获得 $$$n$$$ 银币。请注意,Monocarp 可以任意多次执行两种类型的交换(出售和购买金币换取银币)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le n \le 10^7$$$; $$$1 \le a, b \le 50$$$)。
输出
对于每个测试用例,打印一个整数 - Monocarp 必须完成的最小可能任务数。
示例
输入 #1
4 100 25 30 9999997 25 50 52 50 48 49 50 1
输出 #1
4 400000 1 1
注意
在示例的第一个测试用例中,Monocarp 应该完成 $$$4$$$ 任务,然后将 $$$4$$$ 金币出售为 $$$100$$$ 银币。
在第二个测试用例中,Monocarp 应该完成 $$$400000$$$ 任务,然后将 $$$400000$$$ 金币出售为 $$$10$$$ 百万银币。
在第三个测试用例中,Monocarp 应该完成 $$$1$$$ 任务,以 $$$50$$$ 银币出售金币,以 $$$48$$$ 银币购买金币,然后再次以 $$$50$$$ 银币出售。所以,他将拥有$$$52$$$银币。
在第四个测试用例中,Monocarp 应该完成 $$$1$$$ 任务,然后将他获得的金币出售为 $$$50$$$ 银币。