F. Тортик - ложь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы закончить вечеринку, Алиса решает приготовить для своих друзей несколько блинчиков.

У Алисы есть $$$n$$$ сырых блинчиков, но только $$$2$$$ сковороды. Изначально на сковородах лежат первые $$$min(n,2)$$$ блинчиков, и у всех блинчиков степень готовности равна $$$0$$$.

Чтобы приготовить свои блинчики, Алиса может выполнять следующие две операции любое количество раз:

  • Готовить два блинчика на сковородах в течение $$$1$$$ минуты. Степень готовности блинчика на первой сковороде увеличивается на $$$a$$$, а степень готовности блинчика на второй сковороде увеличивается на $$$b$$$.
  • Подать первый блинчик, переместить второй блинчик на первую сковороду и добавить новый сырой блинчик на вторую сковороду (если ещё остались полностью сырые блинчики). Заметьте, что это не занимает времени и может быть выполнено несколько раз подряд.

Заметьте, что если остался только один блинчик, он будет лежать на первой сковороде и будет получать по $$$a$$$ единиц степени готовности за минуту, пока Алиса не решит подать его.

Блинчик считается идеально приготовленным тогда и только тогда, когда его степень готовности в точности равна $$$k$$$.

Помогите Алисе найти максимальное количество идеально приготовленных блинчиков, которые она может подать.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

На единственной строке каждого набора входных данных содержатся $$$4$$$ целых числа $$$n$$$, $$$a$$$, $$$b$$$ и $$$k$$$ ($$$1 \le n,a,b,k \le 10^9$$$) — количество сырых блинчиков, которое есть у Алисы, увеличение степени готовности за минуту на первой сковороде, увеличение степени готовности за минуту на второй сковороде и степень готовности, которую должен иметь блинчик, чтобы считаться идеально приготовленным.

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

Для каждого набора входных данных выведите максимальное количество идеально приготовленных блинчиков, которое Алиса может приготовить.

Пример
Входные данные
7
17 1 1 1
123456789 987 654 321
3 11 37 111111
987654321 1 2 123456789
100 1 2 1
100 1 2 2
1 1 1 1
Выходные данные
17
0
2
987654320
50
67
1
Примечание

В первом наборе входных данных Алиса может идеально приготовить все блинчики по два за раз. Поэтому максимальное количество идеально приготовленных блинчиков равно $$$17$$$.

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

В третьем наборе входных данных Алиса может оставить первые два блинчика на сковородах на $$$3003$$$ минуты, а затем подать оба из них: один недожаренный и один идеально приготовленный. Для последнего блинчика она оставляет его на сковороде на $$$10\,101$$$ минуту перед подачей, чтобы сделать его идеально приготовленным. Поскольку нет способов идеально приготовить первые два блинчика (к тому моменту, когда первый блинчик станет идеально приготовленным, второй блинчик уже будет пережарен), максимальное количество идеально приготовленных блинчиков равно $$$2$$$.