Minimize Maximum Consecutive Wins

In a series of duels between Player F and Player S, each duel has a decisive result, i.e. either F wins or S wins; there are no draws. The contest rules are as follows:

Given two integers \(x\) and \(y\), Player F wins the overall contest if he wins \(x\) duels before Player S wins \(y\) duels. Conversely, Player S wins the contest if he is the first to win \(y\) duels.

So far, \(n\) duels have been played and the results are recorded in a string \(s\) of length \(n\). The \(i\)-th character of \(s\) is 'F' if Player F won the \(i\)-th duel, or 'S' if Player S won.

Assuming that the contest has not yet been decided (i.e. neither player has reached their threshold), Player F is determined to win the overall contest. In order to win, he is interested in minimizing the strain on his performance by achieving as few consecutive wins as possible in the remaining matches. Formally, he wants to know the minimum possible value of the maximum number of consecutive wins he would have to secure among the future matches in some arrangement that guarantees his eventual victory.

Observation: In the remaining matches, let:

• remainF = \(x - f\), where \(f\) is the number of duels Player F has already won.
• remainS_allowed = \(y - s - 1\), where \(s\) is the number of duels Player S has already won. Note that if Player S wins one more duel beyond this, S will win the contest.

Player F can strategically intersperse his wins with a limited number of losses (i.e. S wins) before the contest ends. By inserting all possible losses among his required wins, he can divide his \(remainF\) wins into \(remainS_allowed + 1\) groups. The goal is to minimize the maximum wins in any group. The minimum required maximum consecutive wins is given by the formula:

[ \text{answer} = \left\lceil \frac{x - f}{y - s} \right\rceil ]

where \(f\) is the count of 'F' in \(s\) and \(s\) is the count of 'S' in \(s\). You are to answer \(T\) queries.

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 10^5\)) denoting the number of queries.

Each query consists of two lines:

• The first line contains two integers \(x\) and \(y\) (\(1 \le x, y \le 10^9\)).
• The second line contains a non-empty string \(s\) consisting only of characters 'F' and 'S', representing the outcomes of the duels played so far. It is guaranteed that the contest has not yet ended (i.e. the number of 'F' is less than \(x\) and the number of 'S' is less than \(y\)).

outputFormat

For each query, output a single integer — the minimum possible value of the maximum number of consecutive wins that Player F must achieve in the remaining matches to guarantee his victory.

sample

3
5 3
F
10 10
FSSF
7 5
SSFF

2
1
2

</p>