Last Sip - Repovive Premier Round 8 | Repovive

24C. Last Sip

1500 pts2s256 MB

There are $n$ cups in a row. Cup $i$ contains $a_i$ units of either tea or coffee. A string $s$ describes their drinks: $s_i=\texttt{T}$ means tea, and $s_i=\texttt{C}$ means coffee.

In one operation, choose two adjacent cups containing different drinks. If their current amounts are $x$ and $y$ , drink $\min(x,y)$ units from each cup. Remove every cup that becomes empty, and close the gaps in the row.

Find the minimum number of cups that can remain after any number of operations.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$s$ has length $n$ and consists only of the characters $\texttt{T}$ and $\texttt{C}$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ s \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

For each test case, print the minimum number of cups that can remain.

Samples

Input

Case 1

3
TCT
2 1 1

Case 2

3
TCC
3 1 2

Explanation

Case 1

Choose cups 2 and 3. Both become empty, leaving only cup 1. The initial row contains 2 more units of tea than coffee, so it cannot become empty.

Case 2

Choose cups 1 and 2 and drink 1 unit from each. The remaining cups contain 2 units of tea and 2 units of coffee. One more operation empties both.

Output

Case 1

Case 2

Input

Case 1

1
C
7

Case 2

8
TTTCCTTT
1 1 2 2 2 2 1 1

Case 3

4
TTTT
2 5 1 4

Explanation

Case 1

There is only one cup, so no operation is possible.

Case 2

Using original cup numbers, first choose cups 3 and 4, emptying both. Next, choose cups 2 and 5, then cups 1 and 5. This leaves cups 6, 7, and 8. Four units of tea must remain. To keep only two cups, both cups 3 and 6 would have to remain with their full 2 units. But while cup 3 survives, the tea in cups 1 and 2 cannot reach any coffee. Thus two remaining cups are impossible.

Case 3

Every cup contains tea, so no operation is possible and all four cups remain.

Output

Case 1

Case 2

Case 3

There are $n$ cups in a row. Cup $i$ contains $a_i$ units of either tea or coffee. A string $s$ describes their drinks: $s_i=\texttt{T}$ means tea, and $s_i=\texttt{C}$ means coffee.

Find the minimum number of cups that can remain after any number of operations.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$s$ has length $n$ and consists only of the characters $\texttt{T}$ and $\texttt{C}$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ s \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

For each test case, print the minimum number of cups that can remain.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

24C. Last Sip

Constraints

Input

Output

Samples

24C. Last Sip

Constraints

Input

Output

Samples