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}$ "(())(())".