Homecoming

题意翻译

### 题目描述 Petya 开完了派对，想回家。 我们可以把整个城市抽象成一条直线，开派对的地方在直线的一端，Petya 的家在直线的另一端。 直线上有一些公交车站（用 'A' 表示）和一些电车站（用 'B' 表示）。 Petya 可以支付 $a$ 元从一个车站坐到另一个车站，但乘车的路程中路过的必须是公交车站（包括起点不包括终点）。 Petya 可以支付 $b$ 元从一个车站坐到另一个车站，但乘车的路程中路过的必须是电车站（包括起点不包括终点）。 但是 Petya 的只有 $p$ 元，所以你要帮她算出她至少要步行几站才能到家？ ### 输入格式 第一行一个整数 $t$ ，表示数据的组数。 对于每组数据，有两行： 第一行三个整数，分别为 $a$ ,$b$ 和 $p$ ，意义见题目描述。 第二行一个字符串，由'A'和'B'组成，表示这条路上的车站。 ### 输出格式 对于每组测试数据，输出一行，包含一个整数，即 Petya 至少要步行几站才能到家。 ### 数据范围 $1 \le t \le 10^4$ ，$1 \le a, b, p \le 10^5 $ ，$ 2 \le |s| \le 10^5 $

题目描述

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

输入输出样例

输入样例 #1

5
2 2 1
BB
1 1 1
AB
3 2 8
AABBBBAABB
5 3 4
BBBBB
2 1 1
ABABAB

输出样例 #1

2
1
3
1
6