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

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

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

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$$$.

#	Name	Rating↕	Solved↕
1750E	Bracket Cost binary search data structures divide and conquer dp greedy strings	2400	1.7k
1654F	Minimal String Xoration bitmasks data structures divide and conquer greedy hashing sortings strings	2800	1.5k
1416C	XOR Inverse bitmasks data structures divide and conquer dp greedy math sortings strings trees	2000	5.2k

Problemset