A. Раунд трип
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Говорят, что если написать 1000 раундов, то в конце будет мультфильм (с)

Петя и Вася очень любят писать раунды Codeforces, Вася поспорил с Петей, что сможет написать больше рейтинговых раундов, чем он. Изначально рейтинг Васи равен $$$R_0$$$. Далее состоится $$$n$$$ раундов, каждый одного из двух типов:

  • div. 1 — рейтинговый для всех участников,
  • div. 2 — рейтинговый для участников с рейтингом строго меньше $$$X$$$, и нерейтинговый для всех остальных.

Участие в нерейтинговом раунде не изменяет рейтинг Васи. Если рейтинг Васи перед рейтинговым контестом равен $$$R$$$, то для любого неотрицательного целого $$$x$$$ в диапазоне от $$$R-D$$$ до $$$R+D$$$ (включительно) Вася может написать раунд так, чтобы после раунда его рейтинг стал равен ровно $$$x$$$ (здесь $$$D$$$ — некоторое положительное целое число). Обратите внимание, что рейтинг никогда не может стать отрицательным.

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

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

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

В первой строке каждого набора указаны целые числа $$$R_0, X, D, n$$$ ($$$0 \leq R_0 \leq 10^9$$$, $$$1 \leq X \leq 10^9$$$, $$$1 \leq D, n \leq 1000$$$) — изначальный рейтинг Васи, граница рейтинга между дивизионами, максимальное изменение рейтинга и количество раундов.

Во второй строке каждого набора входных данных записана строка из $$$n$$$ символов. Каждый символ равен «1» или «2», и означает div. 1 либо div. 2 раунд соответственно..

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^4$$$.

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

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

Пример
Входные данные
4
2100 2100 5 3
222
2098 2100 5 6
111211
2115 2100 226 7
2211121
0 10 4 8
22111121
Выходные данные
0
6
5
8
Примечание

В первом примере, так как $$$R_0 \geq X$$$, то каждый div. 2 раунд для Васи нерейтинговый, и рейтинг Васи никогда не изменится. Следовательно, ответ $$$0$$$.

Во втором примере одной из оптимальных последовательностей изменений рейтинга Васи является последовательность $$$2098 \rightarrow 2103 \rightarrow 2101 \rightarrow 2099 \rightarrow 2097 \rightarrow 2097 \rightarrow 2092$$$.