B. 单挑【普及】

内存限制:256 MiB 时间限制:1000 ms 输入文件: dan.in 输出文件: dan.out
题目类型:传统 评测方式:文本比较

题目描述

小 F 和小 S 经常进行篮球单挑,但小 S 总是被盖帽。

每次单挑的结果一定是小 F 获胜或者小 S 获胜,不存在平局的情况。

由于小 F 和小 S 实力不均衡,于是他们制定规则如下:

给定两个整数 x,y ,若小 F 先赢 x 场,则小 F 获胜。若小 S 先赢 y 场,则小 S 获胜。

现在已经进行了 n 场单挑,这 n 场单挑的结果由一个字符串 s 给出。若 s 的第 i 位为 F,则小 F 赢了第 i 场。若 s 的第 i 位为 S,则小 S 赢了第 i 场。

小 F 想知道,为了取得胜利,后续的比赛中他最多连续胜利的场数最少是多少

你总共需要回答 T 组询问。

输入格式

第一行一个整数 T ,表示共有 T 组数据。

每组数据共两行。

第一行三个整数 n,x,y ,含义与题目描述一致。

第二行一个长度为 n 的字符串 s ,含义与题目描述一致。

输出格式

T 行。

每行一个整数,表示小 F 在后续的比赛中最多连续胜利的场数的最小值。

样例

样例输入 #1

1
5 6 4
SFSFS

样例输出 #1

4

样例输入 #2

1
3 7 3
FFF

样例输出 #2

2

样例输入 #3

1
29 1000 20
FFFSFFFFSFFFFFSFFFSFFFFFFSFFF

样例输出 #3

66

【样例 1 解释】

为了让小 F 获胜,后续的比赛结果只能为 \texttt {FFFF} ,此时最多连续胜利场数为 4

【样例 2 解释】

为了让小 F 获胜,一种可能的后续的比赛结果为 \texttt {FFSFSF} ,此时最多连续胜利场数为 2

请注意,您只需考虑后续的比赛中的最多连续胜场数,而不需要考虑前 n 场。

数据范围与提示

【数据规模与约定】

对于 100 \% 的数据,保证:

  • 1 \leq T \leq 20
  • 1 \leq n \leq 2\times10^5
  • 1 \leq x,y \leq 10^9
  • \forall i \leq n ,保证第 i 场比赛结束后小 S 没有获胜。
  • \forall i < n ,保证第 i 场比赛结束后小 F 没有获胜。
子任务 分值 特殊性质
1 20 n=1
2 20 x,y\leq n
3 20 A
4 20 T=1
5 20
  • 特殊性质 A :第 n 场比赛结束后,小 S 总共获胜 y-1 场。