C. Regular Bracket Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a bracket sequence $$$s$$$ of length $$$n$$$. The string consists of opening brackets '(' and closing brackets ')' only.

In one move,

  • you choose some index $$$i$$$, remove the $$$i-th$$$ character of $$$s$$$ and concatenate the remaining part of string. This move cost $$$a$$$ coins. Example - $$$s$$$ = "(()" choose $$$i=2$$$, remove $$$2nd$$$ character to form "()". $$$$$$OR$$$$$$
  • you choose some index $$$i$$$, remove the $$$i-th$$$ character of $$$s$$$ and insert it after all remaining characters of $$$s$$$. This move cost $$$b$$$ coins. Example - $$$s$$$ = ")(()" choose $$$i=1$$$, remove $$$1st$$$ character and insert in end to form "(())".

Your task is to find the minimum number of coins required to obtain regular bracket sequence from $$$s$$$. You can perform any number of moves (including zero).

Recall what the regular bracket sequence is:

  • $$$Empty$$$ $$$String$$$ is regular bracket sequence.
  • if $$$s$$$ is regular bracket sequence then "(" + $$$s$$$ + ")" is regular bracket sequence.
  • if $$$s$$$ and $$$t$$$ are regular bracket sequences then $$$s + t$$$ is regular bracket sequence.

For example, " ", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

Input

The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains two lines. The first line contains three integer $$$n (1 \le n \le 10^5)$$$: length of string, $$$a ( 1 \le a \le 10^9 )$$$: cost of first operation , $$$b( 1 \le b \le 10^9 )$$$: cost of second operation, all separated by space, and

The second line contains a string consisting of opening and closing brackets only of length $$$n$$$.

It is guaranteed that the total sum of $$$n$$$ is at most $$$10^5$$$.

Output

Print $$$t$$$ answers to the test cases. Each answer must be consisting of single integer — the minimum coins required to obtain a regular bracket sequence from $$$s$$$.

Note: Cost may be greater than $$$2^{32} - 1$$$.

Example
Input
5
2 100 1
)(
2 1 100
)(
3 1 1000
)()
3 1000 1
()(
5 1000000000 1
)))))
Output
1
2
1
1000
5000000000
Note

In the first query — Choose $$$i=1$$$, remove $$$1st$$$ character and insert in end to form "()".

In the second query — Choose $$$i=1$$$, remove $$$1st$$$ character and Choose $$$i=2$$$, remove $$$2nd$$$ character to form " ".

In the third query — Choose $$$i=1$$$, remove $$$1st$$$ character to form "()".