You are given a bracket sequence $s$ of length $n$. The string consists of opening brackets '_(_' and closing brackets '_)_' only.
In one move,
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:
For example, "_ _", "_(())()_", "_(())_" and "_()_" are regular bracket sequences, but "_)(_", "_()(_" and "_)))_" are not.
The first line contains a single integer $t (1 <= t <= 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 <= n <= 10^5)$: length of string, $a (1 <= a <= 10^9)$: cost of first operation , $b (1 <= b <= 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$.
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$.
In the first query — Choose $i = 1$, remove $1 s t$ character and insert in end to form "_()_".
In the second query — Choose $i = 1$, remove $1 s t$ character and Choose $i = 2$, remove $2 n d$ character to form "_ _".
In the third query — Choose $i = 1$, remove $1 s t$ character to form "_()_".
## Input
The first line contains a single integer $t (1 <= t <= 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 <= n <= 10^5)$: length of string, $a (1 <= a <= 10^9)$: cost of first operation , $b (1 <= b <= 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$.
[samples]
## Note
In the first query — Choose $i = 1$, remove $1 s t$ character and insert in end to form "_()_".In the second query — Choose $i = 1$, remove $1 s t$ character and Choose $i = 2$, remove $2 n d$ character to form "_ _".In the third query — Choose $i = 1$, remove $1 s t$ character to form "_()_".
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
Let $ T = \{(n_k, a_k, b_k, s_k) \mid k \in \{1, \dots, t\}\} $ be the set of test cases, where for each $ k $:
- $ n_k \in \mathbb{Z} $ is the length of the bracket sequence.
- $ a_k, b_k \in \mathbb{Z}^+ $ are the costs of two operations.
- $ s_k \in \{ \texttt{(}, \texttt{)} \}^{n_k} $ is a bracket string.
**Operations**
1. **Operation 1 (cost $ a $)**: Remove any single character and insert it at any position.
2. **Operation 2 (cost $ b $)**: Remove any single character (and discard it).
**Constraints**
1. $ 1 \le t \le 10^5 $
2. $ 1 \le n_k \le 10^5 $, $ 1 \le a_k, b_k \le 10^9 $
3. $ \sum_{k=1}^t n_k \le 10^5 $
**Objective**
For each test case $ k $, find the minimum cost to transform $ s_k $ into a *regular bracket sequence* using any number of Operation 1 and/or Operation 2.
Let $ \text{balance} $ be the running sum: +1 for '(', -1 for ')'.
Let $ \text{min\_balance} $ be the minimum value of balance during traversal.
Let $ \text{total\_open} $ be the number of '(' in $ s_k $, $ \text{total\_close} $ be the number of ')' in $ s_k $.
Define:
- $ \text{deficit} = \max(0, -\text{min\_balance}) $ — number of '(' needed to fix prefix imbalance.
- $ \text{excess} = \text{total\_close} - \text{total\_open} $ — surplus closing brackets.
- $ \text{required\_open} = \text{deficit} $
- $ \text{required\_close} = \max(0, \text{total\_open} - \text{total\_close}) $
A regular sequence requires:
- Total open = total close → $ \text{total\_open} = \text{total\_close} $
- Balance never drops below 0
Thus, the number of unmatched closing brackets that must be removed or moved: $ \max(0, -\text{min\_balance}) $
The number of excess brackets to eliminate: $ |\text{total\_open} - \text{total\_close}| $
Let $ r = |\text{total\_open} - \text{total\_close}| $
Let $ d = \max(0, -\text{min\_balance}) $
We must:
- Fix prefix imbalance $ d $: can be done by moving $ d $ closing brackets from front to end (cost $ d \cdot a $) or removing $ d $ closing brackets (cost $ d \cdot b $)
- Fix length imbalance $ r $: must remove $ r $ excess brackets (cost $ r \cdot b $)
**Objective Function**
$$
\min \left( d \cdot a + r \cdot b, \, (d + r) \cdot b \right)
$$