After a long party Petya decided to return home, but he turned out to be at the opposite end of the town from his home. There are $$$n$$$ crossroads in the line in the town, and there is either the bus or the tram station at each crossroad.
The crossroads are represented as a string $$$s$$$ of length $$$n$$$, where $$$s_i = \texttt{A}$$$, if there is a bus station at $$$i$$$-th crossroad, and $$$s_i = \texttt{B}$$$, if there is a tram station at $$$i$$$-th crossroad. Currently Petya is at the first crossroad (which corresponds to $$$s_1$$$) and his goal is to get to the last crossroad (which corresponds to $$$s_n$$$).
If for two crossroads $$$i$$$ and $$$j$$$ for all crossroads $$$i, i+1, \ldots, j-1$$$ there is a bus station, one can pay $$$a$$$ roubles for the bus ticket, and go from $$$i$$$-th crossroad to the $$$j$$$-th crossroad by the bus (it is not necessary to have a bus station at the $$$j$$$-th crossroad). Formally, paying $$$a$$$ roubles Petya can go from $$$i$$$ to $$$j$$$ if $$$s_t = \texttt{A}$$$ for all $$$i \le t < j$$$.
If for two crossroads $$$i$$$ and $$$j$$$ for all crossroads $$$i, i+1, \ldots, j-1$$$ there is a tram station, one can pay $$$b$$$ roubles for the tram ticket, and go from $$$i$$$-th crossroad to the $$$j$$$-th crossroad by the tram (it is not necessary to have a tram station at the $$$j$$$-th crossroad). Formally, paying $$$b$$$ roubles Petya can go from $$$i$$$ to $$$j$$$ if $$$s_t = \texttt{B}$$$ for all $$$i \le t < j$$$.
For example, if $$$s$$$="AABBBAB", $$$a=4$$$ and $$$b=3$$$ then Petya needs:
- buy one bus ticket to get from $$$1$$$ to $$$3$$$,
- buy one tram ticket to get from $$$3$$$ to $$$6$$$,
- buy one bus ticket to get from $$$6$$$ to $$$7$$$.
Thus, in total he needs to spend $$$4+3+4=11$$$ roubles. Please note that the type of the stop at the last crossroad (i.e. the character $$$s_n$$$) does not affect the final expense.
Now Petya is at the first crossroad, and he wants to get to the $$$n$$$-th crossroad. After the party he has left with $$$p$$$ roubles. He's decided to go to some station on foot, and then go to home using only public transport.
Help him to choose the closest crossroad $$$i$$$ to go on foot the first, so he has enough money to get from the $$$i$$$-th crossroad to the $$$n$$$-th, using only tram and bus tickets.
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).
The first line of each test case consists of three integers $$$a, b, p$$$ ($$$1 \le a, b, p \le 10^5$$$) — the cost of bus ticket, the cost of tram ticket and the amount of money Petya has.
The second line of each test case consists of one string $$$s$$$, where $$$s_i = \texttt{A}$$$, if there is a bus station at $$$i$$$-th crossroad, and $$$s_i = \texttt{B}$$$, if there is a tram station at $$$i$$$-th crossroad ($$$2 \le |s| \le 10^5$$$).
It is guaranteed, that the sum of the length of strings $$$s$$$ by all test cases in one test doesn't exceed $$$10^5$$$.
For each test case print one number — the minimal index $$$i$$$ of a crossroad Petya should go on foot. The rest of the path (i.e. from $$$i$$$ to $$$n$$$ he should use public transport).
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
