You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Daemon Targaryen decided to stop looking like a Metin2 character. He turned himself into the most beautiful thing, a bracket sequence.

For a bracket sequence, we can do two kind of operations:

- Select one of its substrings$$$^\dagger$$$ and cyclic shift it to the right. For example, after a cyclic shift to the right, "(())" will become ")(()";
- Insert any bracket, opening '(' or closing ')', wherever you want in the sequence.

We define the cost of a bracket sequence as the minimum number of such operations to make it balanced$$$^\ddagger$$$.

Given a bracket sequence $$$s$$$ of length $$$n$$$, find the sum of costs across all its $$$\frac{n(n+1)}{2}$$$ non-empty substrings. Note that for each substring we calculate the cost independently.

$$$^\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$$$^\ddagger$$$ A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $$$+$$$ and $$$1$$$. For example, sequences "(())()", "()", and "(()(()))" are balanced, while ")(", "(()", and "(()))(" are not.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the bracket sequence.

The second line of each test case contains a string $$$s$$$, consisting only of characters '(' and ')', of length $$$n$$$ — the bracket sequence.

It is guaranteed that sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the sum of costs of all substrings of $$$s$$$.

## Examples
```input
5
1
)
4
)()(
3
())
5
(((((
10
)(())))())
```
```output
1
9
6
35
112
```

## Note
In the first test case, there is the only substring ")". Its cost is $$$1$$$ because we can insert '(' to the beginning of this substring and get a string "()", that is a balanced string.

In the second test case, the cost of each substring of length one is $$$1$$$. The cost of a substring ")(" is $$$1$$$ because we can cyclically shift it to right and get a string "()". The cost of strings ")()" and "()(" is $$$1$$$ because its enough to insert one bracket to each of them. The cost of substring ")()(" is $$$1$$$ because we can cyclically shift it to right and get a string "()()". So there are $$$4 + 2 + 2 + 1 = 9$$$ substring of cost $$$1$$$ and $$$1$$$ substring of cost $$$0$$$. So the sum of the costs is $$$9$$$.

In the third test case,

- "(", the cost is $$$1$$$;
- "()", the cost is $$$0$$$;
- "())", the cost is $$$1$$$;
- ")", the cost is $$$1$$$;
- "))", the cost is $$$2$$$;
- ")", the cost is $$$1$$$.

So the sum of the costs is $$$6$$$.

Now solve the problem and return the code.