Description

Exactly one of FL_sleake and SnowTrace will win a single one-on-one round. There is no situation of a tie.

Due to the uneven strength between FL_sleake and SnowTrace, they have made the rules as follow:

Given two positive integers $x$ and $y$. If FL_sleake wins $x$ rounds before SnowTrace wins $y$ rounds, FL_sleake wins. Otherwise SnowTrace wins.

There have already been $n$ one-on-one rounds, and their results is given as a string $s$ of length $n$. If the $i$-th character of $s$ is F, it means FL_sleake has won the $i$-th round. If the $i$-th character of $s$ is S, it means SnowTrace has won the $i$-th round.

FL_sleake wants to find the minimum number of the maximum winning streak in the following rounds of himself if he wins at last.

Input Format

Each test contains $T$ test cases.

The first line contains a single integer $T$ — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $n,x$ and $y$.

The second line of each test case contains the string $s$ of length $n$.

Output Format

For each test case, output one line containing a single integer, which is the answer of the test case.

1
5 6 4
SFSFS

4

1
3 7 3
FFF

2

1
29 1000 20
FFFSFFFFSFFFFFSFFFSFFFFFFSFFF

66

Hint

Example Explanation

In the first example, in order for FL_sleake to win, he must win all of the following rounds until he wins a total of $6$ rounds. So, he has to win $4$ times in a row.

In the second example, $\texttt{FFSFSF}$ is a possible result of the following rounds. In this case, the maximum winning streak of FL_sleake is $2$.

Note that you only needs to consider the maximum winning streak in the following rounds until he wins. The streak in the first $n$ rounds doesn't matter.

Constraints

Subtasks are used in this problem.

For all tests, it is guaranteed that:

• $1 \leq T \leq 20$
• $1 \leq n \leq 2\times10^5$
• $1 \leq x,y \leq 10^9$
• $\forall i \leq n$，SnowTrace doesn't win after the $i$-th round.
• $\forall i < n$，FL_sleake doesn't win after the $i$-th round.

• Special property $A$: SnowTrace wins $y-1$ rounds after the $n$-th round.