Color the Arrows

There are n arrows drawn in a row on a strip of paper, numbered from 1 to n. Each arrow points either to the left or to the right. Initially, all arrows are painted blue.

In one operation, you can repaint a blue arrow into red. For the first operation, you can choose any arrow. For each subsequent operation, you are only allowed to choose such an arrow that the arrow repainted on the previous operation points in its direction. That is, if the arrow repainted in the previous operation is a left arrow, then, for the current operation, you have to choose an arrow at a smaller index than the previous one. Similarly, if the previous arrow was a right arrow, the current one has to be at a greater index than it. Note that the arrows don't have to be adjacent.

Each arrow has an integer reward for repainting it into red (which can be negative, positive, or zero).

The final score is the sum of the rewards for the repainted arrows. What is the maximum score that can be achieved if you are allowed to perform any number of operations (including zero)?

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

In the first line of each test case, there is a single integer n (1≤n≤3⋅105) — the number of arrows.

In the second line, there is a string consisting of n characters '<' and/or '>' (ASCII codes 60 and 62, respectively).

In the third line, there are n integers c1,c2,…,cn (−109≤ci≤109) — the reward for repainting each arrow.

An additional constraint on the input: the sum of n over all test cases does not exceed 3⋅105.

Output

For each test case, print a single integer — the maximum score that can be achieved if you are allowed to perform any number of operations (including zero).

Note

In the first test case, you can first repaint the arrow at index 2. This arrow points to the right, so in the next operation, you have to choose an arrow to the right of it. Let's repaint the arrow at index 3. This arrow also points to the right, so no more arrows can be repainted. The answer is c2+c3=4+6=10.

In the second test case, you can repaint arrows 3, then 1.

In the third test case, it is most optimal to not repaint any arrows. This will yield an answer of 0, while repainting at least one arrow would lead to a negative answer.

In the fourth test case, you can repaint the arrows in the following order: 3,7,1,5.

In the fifth test case, you can repaint the arrows in the following order: 4,3,2,1,5.

5
3
<>>
5 4 6
5
<><>>
5 -2 4 -3 7
2
>>
-1 -2
8
>>>><<<<
1 -1 1 -1 1 -1 1 -1
5
><<<>
-1 100 100 100 100

10
9
0
4
399