括号序列是由字符 ( 和 ) 组成的字符串。一个括号序列 $s_{1,2,\dots,m}$ 被定义为合法的，当且仅当它满足以下条件之一：

• $s$ 为空。
• $s_1 = \text{`('}$，$s_m = \text{`)'}$，且 $s_{2,3,\dots,m-1}$ 是合法的。
• 存在一个位置 $k$ ($1 \le k < m$)，使得 $s_{1,2,\dots,k}$ 是合法的，且 $s_{k+1,k+2,\dots,m}$ 是合法的。

在括号序列 $s_{1,2,\dots,m}$ 中，两个位置 $i, j$ ($1 \le i < j \le m$) 被称为是匹配的，当且仅当 $s_{i,i+1,\dots,j}$ 和 $s_{i+1,i+2,\dots,j-1}$ 都是合法的。

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，其中保证 $n$ 是偶数。我们通过一个合法的括号序列 $b_1, b_2, \dots, b_n$ 来构造一个新的整数序列 $c_1, c_2, \dots, c_n$，使得对于所有 $1 \le i \le n$，$c_i = a_{p_i}$，其中 $p_i$ 是在 $b_{1,2,\dots,n}$ 中与位置 $i$ 匹配的位置。

求一个合法的括号序列 $b_{1,2,\dots,n}$，使得 $c_{1,2,\dots,n}$ 的字典序最小。如果有多个解，输出其中任意一个。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2.5 \times 10^5$)，表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)，表示序列 $a$ 的长度，保证 $n$ 是偶数。

第二行包含 $n$ 个空格分隔的整数，表示 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个长度为 $n$ 的字符串，表示 $b_{1,2,\dots,n}$。

样例

输入样例 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

输出样例 1

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