CF1315B.Homecoming

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 \lt 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 \lt 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.

派蒂亚参加完一场漫长的聚会后决定回家，但他发现自己身处城镇的最远端，与家正好相对。镇上共有 $n$ 个十字路口排成一条直线，每个十字路口处要么设有公交车站，要么设有有轨电车站。

这些十字路口用一个长度为 $n$ 的字符串 $s$ 表示：若第 $i$ 个十字路口处是公交车站，则 $s_i = \texttt{A}$；若为有轨电车站，则 $s_i = \texttt{B}$。目前派蒂亚位于第一个十字路口（对应 $s_1$），他的目标是到达最后一个十字路口（对应 $s_n$）。

若对两个十字路口 $i$ 和 $j$，在所有从 $i$ 到 $j-1$ 的十字路口（即 $i,\, i+1,\, \ldots,\, j-1$）上均为公交车站，则可花费 $a$ 卢布购买一张公交车票，乘坐公交车从第 $i$ 个十字路口直达第 $j$ 个十字路口（注意：第 $j$ 个十字路口本身不必是公交车站）。形式化地说，只要对所有满足 $i \le t < j$ 的 $t$ 均有 $s_t = \texttt{A}$，那么花费 $a$ 卢布，派蒂亚即可从 $i$ 到达 $j$。

若对两个十字路口 $i$ 和 $j$，在所有从 $i$ 到 $j-1$ 的十字路口（即 $i,\, i+1,\, \ldots,\, j-1$）上均为有轨电车站，则可花费 $b$ 卢布购买一张有轨电车票，乘坐有轨电车从第 $i$ 个十字路口直达第 $j$ 个十字路口（注意：第 $j$ 个十字路口本身不必是有轨电车站）。形式化地说，只要对所有满足 $i \le t < j$ 的 $t$ 均有 $s_t = \texttt{B}$，那么花费 $b$ 卢布，派蒂亚即可从 $i$ 到达 $j$。

例如，若 $s = \texttt{AABBBAB}$，$a = 4$，$b = 3$，则派蒂亚需要：

• 购买一张公交车票，从第 $1$ 个十字路口到达第 $3$ 个十字路口；
• 购买一张有轨电车票，从第 $3$ 个十字路口到达第 $6$ 个十字路口；
• 购买一张公交车票，从第 $6$ 个十字路口到达第 $7$ 个十字路口。

因此，他总共需花费 $4 + 3 + 4 = 11$ 卢布。请注意：最后一个十字路口处的站点类型（即字符 $s_n$）并不影响总费用。

现在派蒂亚位于第一个十字路口，他希望抵达第 $n$ 个十字路口。聚会结束后，他身上仅剩 $p$ 卢布。他决定先步行前往某个十字路口，然后仅依靠公共交通（公交或有轨电车）回家。

请帮他选择离起点最近的十字路口 $i$（即最小的 $i$），使得他从该十字路口 $i$ 出发，仅使用公交和有轨电车票，便能以不超过 $p$ 卢布的费用抵达第 $n$ 个十字路口。

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$.

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。

每个测试用例的第一行包含三个整数 $a, b, p$（$1 \le a, b, p \le 10^5$）—— 分别表示公交车票价格、有轨电车票价格以及 Petya 拥有的钱数。

每个测试用例的第二行包含一个字符串 $s$，其中若第 $i$ 个路口处为公交车站，则 $s_i = \texttt{A}$；若为有轨电车站，则 $s_i = \texttt{B}$（$2 \le |s| \le 10^5$）。

保证：所有测试用例中字符串 $s$ 的长度总和不超过 $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).

对于每个测试用例，输出一个数字——Petya 应该步行前往的十字路口的最小索引 $i$。路径的其余部分（即从 $i$ 到 $n$）他应乘坐公共交通工具。