A parentheses sequence is a string composed of the characters ( and ). A parentheses sequence $s_{1,2,\ldots,m}$ is defined as valid if it satisfies one of the following conditions:
- $s$ is empty.
- $s_1 = $
(, $s_m = $), and $s_{2,3,\ldots,m-1}$ is valid. - There exists a position $k$ ($1 \le k < m$) such that $s_{1,2,\ldots,k}$ is valid, and $s_{k+1,k+2,\ldots,m}$ is valid.
Two positions $i, j$ ($1 \le i < j \le m$) in the parentheses sequence $s_{1,2,\ldots,m}$ are said to be matched if and only if both $s_{i,i+1,\ldots,j}$ and $s_{i+1,i+2,\ldots,j-1}$ are valid.
Given an integer sequence of length $n$, $a_1, a_2, \ldots, a_n$, where $n$ is guaranteed to be even. We construct a new integer sequence $c_1, c_2, \ldots, c_n$ through a valid parentheses sequence $b_1, b_2, \ldots, b_n$, such that $\forall 1 \le i \le n, c_i = a_{p_i}$, where $p_i$ is the position matched with position $i$ in $b_{1,2,\ldots,n}$.
Find a valid parentheses sequence $b_{1,2,\ldots,n}$ such that the lexicographical order of $c_{1,2,\ldots,n}$ is minimized. If there are multiple solutions, output any one of them.
Input
The first line contains an integer $T$ ($1 \le T \le 2.5 \times 10^5$), indicating the number of test cases.
For each test case:
The first line contains an integer $n$ ($1 \le n \le 5 \times 10^5$), indicating the length of the sequence $a$, and it is guaranteed that $n$ is even.
The second line contains $n$ space-separated integers, representing $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
It is guaranteed that the sum of $n$ does not exceed $5 \times 10^5$.
Output
For each test case, output a line containing a string of length $n$, representing $b_{1,2,\ldots,n}$.
Examples
Input 1
5 6 4 1 5 4 1 1 4 1 2 3 2 4 1 3 1 2 2 2 1 8 8 5 2 6 1 4 3 7
Output 1
((())) ()() (()) () ((()))()