为了结束聚会,爱丽丝决定为她的朋友们做一些煎饼。
爱丽丝有 $$$n$$$ 未煮过的煎饼,但只有 $$$2$$$ 平底锅。最初,第一个 $$$min(n,2)$$$ 煎饼放在平底锅上,所有煎饼都有熟度 $$$0$$$。
为了煮煎饼,Alice 可以执行以下两个操作任意多次:
- 将两个煎饼放在平底锅上煮 $$$1$$$ 分钟。第一个锅上的煎饼的熟度增加 $$$a$$$,第二个锅上的煎饼的熟度增加 $$$b$$$。
- 提供第一个煎饼,将第二个煎饼移到第一个平底锅中,然后将新的未煮熟的煎饼添加到第二个平底锅中(如果还剩下任何完全未煮熟的煎饼)。请注意,这不需要时间,并且可以连续完成多次。
请注意,如果只剩下一个煎饼,它将放在第一个平底锅上,每分钟获得 $$$a$$$ 熟度,直到 Alice 决定提供它。
煎饼完全煮熟当且仅当其熟度恰好为$$$k$$$。
帮助爱丽丝找到她可以提供的最多数量的完全煮熟的煎饼。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
测试用例中唯一的一行包含 $$$4$$$ 整数 $$$n$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le n,a,b,k \le 10^9$$$) — Alice 的煎饼面糊数量、每分钟结束时第一个平底锅上煎饼的熟度、金额第二个平底锅上的煎饼在每分钟结束时获得的熟度,以及煎饼需要完全煮熟的熟度。
输出
对于每个测试用例,输出 Alice 可以制作的完美煮熟的煎饼的最大数量。
示例
输入复制
717 1 1 1123456789 987 654 3213 11 37 111111987654321 1 2 123456789100 1 2 1100 1 2 21 1 1 1
输出复制
170298765432050671
注意
在第一个测试用例中,Alice 可以完美地烹饪两个一批的所有煎饼。因此,完美煮熟的煎饼的最大数量为 $$$17$$$。
在第二个测试用例中,爱丽丝总是会把所有煎饼煮过头,因为两个平底锅都太热了。因此,完全煮熟的煎饼的最大数量为 $$$0$$$。
在第三个测试用例中,Alice 可以将前两块煎饼放在平底锅上 $$$3003$$$ 分钟,然后将两块煎饼分别上桌,一个未煮熟,一个完全煮熟。对于最后一块煎饼,她将其放在平底锅上 $$$10\,101$$$ 分钟,然后才上桌,使其完全煮熟。由于没有办法完美地烹饪前两个煎饼(当第一个煎饼完全煮熟时,第二个煎饼就会煮过头),因此完美煮熟的煎饼的最大数量为$$$2$$$。