Make Valid Parentheses

You are given a string s consisting solely of characters (' and ')'. The string s may be invalid due to unmatched parentheses. Your task is to remove the minimum number of parentheses so that the resulting string is valid.

A valid parentheses sequence is one in which every opening parenthesis has a corresponding closing parenthesis and the pairs are properly nested. In formal terms, if we require that

$$\text{Valid}(s) \iff \text{for every prefix of } s,\; \#('(') \ge \#(')') \quad \text{and} \quad \#('(') = \#(')') \text{ in total}, $$

then your job is to output a valid sequence after the minimal removals. If the sequence is already valid, output it unchanged. Note that if there are multiple ways to obtain a valid sequence by removing the minimal number of parentheses, any one of them will be accepted.

Constraints: 1 ≤ |s| ≤ 100,000, and s consists only of the characters '(' and ')'.

inputFormat

The input begins with an integer T (T ≥ 1), representing the number of test cases. Each of the next T lines contains a single string of parentheses. Each string will contain at least 1 and at most 100,000 characters.

outputFormat

For each test case, output a single line containing the valid parentheses sequence obtained after removing the minimum number of invalid parentheses. If the result is an empty string, output an empty line.## sample

4
()(())
((())()
(()))
((())

()(())
(())()
(())
(())

</p>