You are given a bracket string $$$s$$$ of length $$$n$$$. You can apply the following operations arbitrary number of times (possibly, zero) and in any order:

Choose an index $$$1 \leq i \lt |s|$$$ such that $$$s_i = s_{i+1} = \texttt{(}$$$, and replace both $$$s_i$$$ and $$$s_{i+1}$$$ with $$$\texttt{)}$$$.
Choose an index $$$1 \leq i \lt |s|$$$ such that $$$s_i = s_{i+1} = \texttt{)}$$$, and replace both $$$s_i$$$ and $$$s_{i+1}$$$ with $$$\texttt{(}$$$.

Find a regular bracket sequence$$$^{\text{∗}}$$$ $$$t$$$ which can be obtained from $$$s$$$ by applying the operations described above, or print $$$-1$$$ if there is no such $$$t$$$.

$$$^{\text{∗}}$$$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example: the bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"); the bracket sequences ")(", "(" and ")" are not.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the string.

The second line contains a single string $$$s$$$ — a sequence of the characters ( and ) of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case output a regular bracket string $$$t$$$ which can be obtained from $$$s$$$ or print $$$-1$$$ if there is no such $$$t$$$.

Note

In the first testcase, the string "()()" is already a regular bracket sequence. No changes needed.

In the second and third testcases it's impossible to reach a regular bracket string from $$$s$$$.

In the fourth testcase we can do the following:

"))))))))" $$$\xrightarrow{i = 1}$$$ "(())))))"

"(())))))" $$$\xrightarrow{i = 5}$$$ "(())(())".

Make Good

Examples