B. Юбилейные монеты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп собирается сделать покупку на ровно $$$m$$$ бурлей.

У него есть два типа монет в следующем количестве:

  • монеты номиналом $$$1$$$ бурль: $$$a_1$$$ обычных монет и бесконечно много юбилейных монет;
  • монеты номиналом $$$k$$$ бурлей: $$$a_k$$$ обычных монет и бесконечно много юбилейных монет.

Монокарп планирует совершить покупку так, чтобы не получить сдачи — суммарный номинал предоставленных монет должен быть ровно $$$m$$$. Он может использовать и обычные, и юбилейные монеты. Однако, он хочет потратить как можно меньше юбилейных монет.

Какое наименьшее суммарное количество юбилейных монет Монокарп может потратить на покупку?

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — количество наборов входных данных.

В единственной строке каждого набора входных данных записаны четыре целых числа $$$m, k, a_1$$$ и $$$a_k$$$ ($$$1 \le m \le 10^8$$$; $$$2 \le k \le 10^8$$$; $$$0 \le a_1, a_k \le 10^8$$$) — стоимость покупки, номинал второго типа монет и количества обычных монет каждого из двух типов, соответственно.

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

На каждый набор входных данных выведите одно целое число — наименьшее суммарное количество юбилейных монет, которые Монокарп может потратить на покупку.

Пример
Входные данные
4
11 3 0 0
11 3 20 20
11 3 6 1
100000000 2 0 0
Выходные данные
5
0
1
50000000
Примечание

В первом наборе входных данных нет обычных монет ни одного из типов. Монокарп может использовать $$$2$$$ юбилейные монеты номиналом $$$1$$$ бурль и $$$3$$$ юбилейные монеты номиналом $$$3$$$ (так как $$$k=3$$$) бурля, чтобы получить суммарно $$$11$$$ бурлей за $$$5$$$ юбилейных монет.

Во втором наборе у Монокарпа очень много обычных монет обоих типов. Он может использовать $$$11$$$ монет номиналом $$$1$$$ бурль, например. Обратите внимание, что Монокарп не обязан минимизировать суммарное количество использованных монет. Таким образом, он использует $$$0$$$ юбилейных монет.

В третьем наборе Монокарп может использовать $$$5$$$ обычных монет номиналом $$$1$$$ бурль и $$$1$$$ обычную монету номиналом $$$3$$$ бурля. Так он получит $$$8$$$ бурлей суммарно, когда ему нужно $$$11$$$. Так что $$$1$$$ юбилейной монеты номиналом $$$3$$$ бурля хватит.