Background

由于小鳄鱼经常被wyy打得找不着北，分不清左右，于是小鳄鱼想请你帮忙分清楚左右。

wyy帅照

Description

有一个由 n 个单元格组成的长条，从左到右的编号为 1 到 n 。在 i /th单元格中，有一个正整数 $a_i$ 和一个字母 $s_i$，其中所有的 $s_i$ 不是 "L " 就是 "R"。

小鳄鱼邀请您尝试进行任意数量(可能为零)的运算，以获得尽可能高的分数。

在一次操作中，您可以选择两个索引 l 和 r ( 1≤l<r≤n )，这样 $s_l$ = 'L'， $s_r$ = 'R'，然后进行以下操作：

• 为当前积分加上 $a_l$+$a_{l+1}$.....$a_r$+$a_{r+1}$ 分；
• 将$s_l$ 和 $s_r$ 替换为'.'，这意味着您不能再选择这些索引。

例如，请考虑以下条带：

您可以先选择 $l = 1$ ， $r = 2$ ，并将 $3 + 5 = 8$ 添加到您的分数中。

然后选择 $l = 3$ ， $r = 6$ 并将 $1 + 4 + 3 + 2 = 10$ 添加到您的分数中。

因此，不可能再进行其他操作，最终得分是 18 。

最大得分是多少？

Format

Input

第一行包含一个整数 t ( 1≤t≤1e4) - 测试用例数。

每个测试用例的第一行包含一个整数 n ( 2≤n≤2e5 ) --条带长度。

每个测试用例的第二行包含 n 个整数 $a_1$,$a_2$.....$a_n$ ( 1≤$a_i$≤1e5 ) - 写在条形图上的数字。

每个测试用例的第三行包含由 n 个字符 "L "和 "R "组成的字符串 s 。

保证所有测试用例中 n 的值之和不超过 2e5 。

Output

对于每个测试用例，输出一个整数--可能得到的最大分数。

Samples

4
6
3 5 1 4 3 2
LRLLLR
2
2 8
LR
2
3 9
RL
5
1 2 3 4 5
LRLRR

18
10
0
22

Limitation

1s, 1024KiB for each test case.