First, let's consider a way to determine if a sequence of parentheses is valid. In the given sequence, we replace each open parenthesis with ~+1~, and ~-1~ for closed. Then we take the prefix sums over this sequence. It can easily be shown that a sequence of parentheses is valid if and only if every prefix sum value is ~\ge 0~ and the total sum equals ~0~.

In the first subtask, for each test case, we can try out all ~2^n~ possibilities. Since the worst case is when ~n~ is maximal and the number of test cases is ~\frac t n~, the total time complexity is ~\mathcal O(2^n \frac t n)~.

In the second subtask, if there are two open parentheses in pair, it is better to choose the one on the left, and if there are two closed parentheses in a pair, it is better to choose the right one. The proof of this fact is a consequence of the characterization of valid sequences discussed in the first paragraph.

For the third subtask, we can imagine having ~n~ empty slots and for each slot having a choice between two parentheses. If the two parentheses in a pair are the same, then we don't really have a choice and we are free to choose any of the two for the corresponding slot. If the parentheses in a pair are different, we have a choice between placing an open or a closed parenthesis in this slot. Regarding the slots for which we have a choice, it's best to choose in such a way that there is a prefix of open parentheses and a suffix of closed parentheses. Exactly how many open/closed parentheses should there be is determined unambiguously from the fact that there should be an equal number of open and closed parentheses in total. In the end, we also check if the formed selection is valid.

For the whole solution, we can picture a choice of parentheses in the following way. We have a sequence of numbers ~0~, ~1~ or ~-1~ of length ~2n~. For each pair of parentheses, we discard one of them and place a ~0~ in its position, and we choose the other one and place a ~+1~ or ~-1~ depending on whether it is an open or a closed parenthesis. This leaves us with a sequence of ~n~ zeroes and ~n~ values ~\pm 1~ over which we take the prefix sums to check whether it's valid.

Similarly as in the second subtask, if two parentheses in a pair are the same, we choose the left one if they are open, and the right one if they are closed. What remains are the pairs of type () and )(. Initially, for each such pair, we'll choose the closed parenthesis, and then we have to decide for some of these pairs to switch our choice back to open. If a pair of parentheses is on positions ~a~ and ~b~ and if we decide to switch, let's consider what effect this has on the array of prefix sums. Regardless of whether we are dealing with a pair of type () or )(, the effect is that we add ~+1~ on the suffix starting from ~a~ and ~-1~ on the suffix starting from ~b~. Therefore, we can represent each pair of parentheses as a range ~[a, b]~, and some of these ranges ought to be activated, that is, we should add ~+1~ on the mentioned suffixes. Since there should be an equal number of open and closed parentheses in total, it is possible to precisely determine how many ranges should become activated.

What remains is to determine which ranges to activate. We claim that the choice should be done in the following manner: in the array of prefix sums, we find the leftmost position with a negative value, call it ~c~. It is clear that we should choose at least one range that will make this value nonnegative, so we should activate at least one range ~[a, b]~ such that ~a \le c~. Out of all such ranges, it is optimal to choose the one which minimizes ~b~. By repeating this procedure, we obtain a solution, and if at some point there is no range which meets the conditions, the answer is -1. Implementing this process can be done with data structures such as a segment tree, a set or by a sweep line on the array by storing information for suffix updates on future positions in the array.