Balancing Parentheses

You are given T strings, each consisting solely of the characters ( and ). For each string, your task is to add the minimum number of parentheses (at the beginning or end of the string) to balance it. A string is balanced if for every opening parenthesis ( there is a corresponding closing parenthesis ) in the correct order.

The solution should process multiple test cases in one run. Read input from standard input and write the result to standard output. Use the least number of additional parentheses necessary to achieve balance.

The balancing procedure is as follows:

[ \text{For each string } s:\ \quad \text{Initialize } left_needed = 0 \text{ and } right_needed = 0.\ \quad For each character c in s, do:\ \quad\quad If c = '(' then increment (right_needed) by 1.\ \quad\quad If c = ')' and (right_needed > 0), then decrement (right_needed) by 1; otherwise, increment (left_needed) by 1.\ \quad The balanced string is formed as: ( (^{left_needed} + s + )^{right_needed} ). ]

Output each balanced string on a new line in the order of the input test cases.

inputFormat

The first line contains a single integer T (1 ≤ T ≤ 10^5), representing the number of strings to process. Each of the following T lines contains a non-empty string consisting only of the characters '(' and ')'.

outputFormat

Output T lines, where each line is the balanced version of the corresponding input string.

## sample

1
)

()

</p>