Вова играет в компьютерную игру. Всего в игре есть \(n\) ходов и Вова очень хочет сыграть каждый из них. Изначальный заряд батареи его ноутбука (то есть заряд перед началом игры) равен \(k\).
В течение каждого хода Вова может выбрать, что именно делать:
- Если текущий заряд батареи его ноутбука строго больше, чем \(a\), то Вова может просто играть, и тогда заряд батареи его ноутбука уменьшится на \(a\);
- если текущий заряд батареи его ноутбука строго больше, чем \(b\) (\(b<a\)), то Вова может играть и заряжать свой ноутбук, и тогда заряд батареи его ноутбука уменьшится на \(b\);
- если текущий заряд батареи его ноутбука меньше либо равен, чем \(a\) и \(b\) одновременно, то Вова не может сделать ничего и проигрывает игру.
Независимо от ходов Вовы заряд батареи ноутбука всегда уменьшается.
Вова хочет завершить игру (Вова может завершить игру, если после каждого из \(n\) ходов заряд батареи его ноутбука строго больше \(0\)). Вове необходимо сыграть ровно \(n\) ходов. Среди всех возможных способов завершить игру Вова хочет выбрать такой, в котором количество ходов, где он просто играет (ход первого типа) является максимально возможным. Также возможно, что Вова в принципе не может завершить игру.
Ваша задача — найти максимально возможное количество ходов, которое Вова может просто играть (делать ход первого типа) или сообщить, что Вова не может завершить игру.
Вам необходимо ответить на \(q\) независимых запросов.
Выходные данные
Для каждого запроса выведите одно целое число: -1, если Вова не может завершить игру или же максимальное количество ходов, в которые Вова может просто играть (делать ход первого типа) в ином случае.
Примечание
В первом запросе тестового примера Вова может просто играть \(4\) хода и потратить \(12\) единиц заряда, а затем один ход играть и заряжать и потратить еще \(2\) единицы. Таким образом, оставшийся заряд батареи будет равен \(1\).
Во втором запросе тестового примера Вова не может завершить игру, потому что даже если он будет играть и заряжать батарею в течение каждого хода, то заряд батареи его ноутбука будет равен \(0\) после последнего хода.
Примеры
| № | Входные данные | Выходные данные |
|
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
|