Problem Statement

You are given a string $S$ of length $N$ consisting of A and B. It is guaranteed that the number of As in $S$ is at most $\frac{N+1}{2}$. Additionally, you are given a sequence of positive integers $(x_1, \ldots, x_{N-1})$.

On this string, you can repeatedly perform the following operation:

• Choose an integer $i$ such that $1\leq i\leq N-1$, and swap the $i$-th and $(i+1)$-th characters of $S$. The cost of this operation is $x_i$.

Your goal is to rearrange $S$ so that no two As are adjacent. Find the minimum total cost required to achieve this goal.

$T$ test cases are given; solve each of them.

Constraints

• $1\leq T\leq 10^5$
• $2\leq N\leq 10^6$
• $S$ is a string of length $N$ consisting of A and B.
• The number of As in $S$ is at most $\frac{N+1}{2}$.
• $1\leq x_i \leq 10^6$
• The sum of $N$ over all test cases in a single input is at most $10^6$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

N
S
x_1 \ldots x_{N-1}

Output

Print $T$ lines. The $i$-th line should contain the minimum total cost required to rearrange $S$ so that no two As are adjacent for the $i$-th test case.