C. Компьютерная игра
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вова играет в компьютерную игру. Всего в игре есть $$$n$$$ ходов и Вова очень хочет сыграть каждый из них. Изначальный заряд батареи его ноутбука (то есть заряд перед началом игры) равен $$$k$$$.

В течение каждого хода Вова может выбрать, что именно делать:

  • Если текущий заряд батареи его ноутбука строго больше, чем $$$a$$$, то Вова может просто играть, и тогда заряд батареи его ноутбука уменьшится на $$$a$$$;
  • если текущий заряд батареи его ноутбука строго больше, чем $$$b$$$ ($$$b<a$$$), то Вова может играть и заряжать свой ноутбук, и тогда заряд батареи его ноутбука уменьшится на $$$b$$$;
  • если текущий заряд батареи его ноутбука меньше либо равен, чем $$$a$$$ и $$$b$$$ одновременно, то Вова не может сделать ничего и проигрывает игру.

Независимо от ходов Вовы заряд батареи ноутбука всегда уменьшается.

Вова хочет завершить игру (Вова может завершить игру, если после каждого из $$$n$$$ ходов заряд батареи его ноутбука строго больше $$$0$$$). Вове необходимо сыграть ровно $$$n$$$ ходов. Среди всех возможных способов завершить игру Вова хочет выбрать такой, в котором количество ходов, где он просто играет (ход первого типа) является максимально возможным. Также возможно, что Вова в принципе не может завершить игру.

Ваша задача — найти максимально возможное количество ходов, которое Вова может просто играть (делать ход первого типа) или сообщить, что Вова не может завершить игру.

Вам необходимо ответить на $$$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$$$) — изначальный заряд батареи ноутбука Вовы, количество ходов в игре и значения $$$a$$$ и $$$b$$$, соответственно.

Выходные данные

Для каждого запроса выведите одно целое число: -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
Выходные данные
4
-1
5
2
0
1
Примечание

В первом запросе тестового примера Вова может просто играть $$$4$$$ хода и потратить $$$12$$$ единиц заряда, а затем один ход играть и заряжать и потратить еще $$$2$$$ единицы. Таким образом, оставшийся заряд батареи будет равен $$$1$$$.

Во втором запросе тестового примера Вова не может завершить игру, потому что даже если он будет играть и заряжать батарею в течение каждого хода, то заряд батареи его ноутбука будет равен $$$0$$$ после последнего хода.