Vova 正在玩电脑游戏。游戏中总共有 $$$n$$$ 个回合,Vova 真的很想玩所有回合。他的笔记本电脑电池的初始电量(即游戏开始前的电量)为 $$$k$$$。
在每个回合中,Vova 可以选择要做什么:
- 如果他的笔记本电脑电池的当前电量严格大于$$$a$$$,Vova可以直接玩,然后他的笔记本电脑电池的电量将减少$$$a$$$;
- 如果他的笔记本电脑电池的当前电量严格大于$$$b$$$ ($$$b<a$$$),Vova可以玩他的笔记本电脑并为其充电,然后他的笔记本电脑电池的电量将减少$$$b$$$;
- 如果他的笔记本电脑电池的当前电量同时小于或等于 $$$a$$$ 和 $$$b$$$,则 Vova 无法执行任何操作并输掉游戏。
无论 Vova 转动多少次,笔记本电脑电池的电量始终会减少。
Vova 想要完成游戏(如果在每次 $$$n$$$ 回合后笔记本电脑电池的电量严格大于 $$$0$$$,则 Vova 可以完成游戏)。 Vova 必须精确地玩 $$$n$$$ 个回合。在所有可能的完成游戏的方式中,Vova 希望选择他刚刚玩时的回合数(第一类回合)尽可能最大的一种。 Vova 有可能根本无法完成游戏。
你的任务是找出 Vova 可以玩的最大可能回合数(进行第一种类型的回合)或报告 Vova 无法完成游戏。
您必须回答 $$$q$$$ 独立查询。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。每个查询都由一行表示。
查询中唯一的一行包含四个整数 $$$k、n、a$$$ 和 $$$b$$$ ($$$1 \le k, n \le 10^9, 1 \le b < a \le 10^9$$$) — Vova 笔记本电脑电池的初始电量、游戏的回合数以及相应的值 $$$a$$$ 和 $$$b$$$。
输出
对于每个查询,打印一个整数:如果 Vova 无法完成游戏,则打印一个整数:-1,否则 Vova 可以玩的最大回合数(进行第一个类型的回合)。
示例
输入 #1
6 15 5 3 2 15 5 4 3 15 5 2 1 15 5 5 1 16 7 5 2 20 5 7 3
输出 #1
4 -1 5 2 0 1
注意
在第一个示例查询中,Vova 可以只玩 $$$4$$$ 回合并花费 $$$12$$$ 单位的费用,然后玩一回合并收费并花费 $$$2$$$ 单位。因此电池的剩余电量将为 $$$1$$$。
在第二个示例中,查询 Vova 无法完成游戏,因为即使他在每个回合中玩游戏并为电池充电,笔记本电脑电池的电量在最后一个回合后也将是 $$$0$$$。