Move Brackets#11788
A bracket sequence of length is given, containing exactly opening brackets '(' and closing brackets ')'.
In one move, you can select a single bracket and move it to the beginning or the end of the string (i.e., you can choose some index , remove the -th character from , and insert it before or after all other characters in ).
Find the minimum number of moves required to transform into a valid bracket sequence. It is guaranteed that such a transformation is always possible.
Definition of a valid bracket sequence:
The string is a valid bracket sequence.
If is a valid bracket sequence, then the string is also a valid bracket sequence.
If and are valid bracket sequences, then their concatenation is also a valid bracket sequence.
For example, the strings "()()", "(())()", "(())" and are valid bracket sequences, while ")(", "()(" and are not.
The first line contains the number of test cases t~(1 \le t \le 2000).
Each of the following lines represents a separate test case and contains a string of even length, consisting of opening brackets and closing brackets ( is an even number).
For each test case, print the minimum number of moves required to transform the string into a valid bracket sequence. It is guaranteed that a solution always exists.
Example 1