После долгой вечеринки Петя захотел поехать домой, но обнаружил себя в другом конце города. В городе есть $$$n$$$ перекрестков, расположенных в ряд, и на каждом перекрестке есть остановка, на которой можно сесть либо на автобус, либо на троллейбус.
Перекрестки можно задать как строку $$$s$$$ длины $$$n$$$, где $$$s_i = \texttt{A}$$$, если на $$$i$$$-м перекрестке есть автобусная станция, и $$$s_i = \texttt{B}$$$, если на $$$i$$$-м перекрестке есть троллейбусная станция. Сейчас Петя находится на первом перекрестке (которому соответствует $$$s_1$$$), и ему нужно попасть на последний перекресток (которому соответствует $$$s_n$$$).
Если для двух перекрестков $$$i$$$ и $$$j$$$ на всех перекрестках $$$i, i+1, \ldots, j-1$$$ есть автобусная остановка, то можно заплатить $$$a$$$ рублей за билет на автобус, и доехать с $$$i$$$-й остановки до $$$j$$$-й (на $$$j$$$-й остановке не обязательно иметь возможность сесть на автобус). Формально, заплатив $$$a$$$ рублей Петя может добраться из $$$i$$$ до $$$j$$$, если $$$s_t = \texttt{A}$$$ для всех $$$i \le t < j$$$.
Если для двух перекрестков $$$i$$$ и $$$j$$$ на всех перекрестках $$$i, i+1, \ldots, j-1$$$ есть троллейбусная остановка, то можно заплатить $$$b$$$ рублей за билет на троллейбус, и доехать с $$$i$$$-й остановки до $$$j$$$-й (на $$$j$$$-й остановке не обязательно иметь возможность сесть на троллейбус). Формально, заплатив $$$b$$$ рублей Петя может добраться из $$$i$$$ до $$$j$$$, если $$$s_t = \texttt{B}$$$ для всех $$$i \le t < j$$$.
Например, если $$$s$$$=«AABBBAB», $$$a=4$$$ и $$$b=3$$$, то Петя может:
- купить билет на автобус, чтобы добраться от $$$1$$$ до $$$3$$$,
- купить билет на троллейбус, чтобы добраться от $$$3$$$ до $$$6$$$,
- купить билет на автобус, чтобы добраться от $$$6$$$ до $$$7$$$.
Так, в общем ему нужно потратить $$$4+3+4=11$$$ рублей. Обратите внимание, что остановка на последнем перекрестке (т.е. символ $$$s_n$$$) не влияет на итоговую стоимость.
Сейчас Петя находится на первом перекрестке, и он хочет попасть на $$$n$$$-й перекресток. После вечеринки у него осталось всего $$$p$$$ рублей, и он хочет попасть домой. Он решил пройти несколько перекрестков пешком, а после этого доехать домой на общественном транспорте. Помогите ему выбрать ближайший перекресток $$$i$$$ к первому так, чтобы ему хватило денег добраться с $$$i$$$-го перекрестка до $$$n$$$-го, используя лишь поездки на автобусах и троллейбусах.
Каждый тест состоит из одного или более наборов входных данных. В первой строке записано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$).
В первой строке набора даны три целых числа $$$a, b, p$$$ — стоимость билета на автобус, стоимость билета на троллейбус, и количество денег у Пети соответственно ($$$1 \le a, b, p \le 10^5$$$).
Во второй строке набора дана строка $$$s$$$, в которой $$$s_i = \texttt{A}$$$, если на $$$i$$$-м перекрестке можно сесть на автобус, и $$$s_i = \texttt{B}$$$, если на $$$i$$$-м перекрестке можно сесть на троллейбус ($$$2 \le |s| \le 10^5$$$).
Гарантируется, что сумма длин строк $$$s$$$ по всем наборам входных данных в тесте не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальный номер перекрестка $$$i$$$, до которого Пете придется идти пешком. Оставшуюся часть пути (т.е. от $$$i$$$ до $$$n$$$) он должен ехать на общественном транспорте.
5 2 2 1 BB 1 1 1 AB 3 2 8 AABBBBAABB 5 3 4 BBBBB 2 1 1 ABABAB
2 1 3 1 6
