B'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: 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. Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= q t <= q 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 <= n <= 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 . For each test case, print a single integer -- the sum of costs of all substrings of s . 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 becaus'...