F. Fanfan's Bracket Sequence
time limit per test
1 second
memory limit per test
1024 MB
input
standard input
output
standard output

Fanfan has a valid bracket sequence $$$s$$$ containing $$$n$$$ bracket pairs, and all bracket pairs are numbered from $$$1$$$ to $$$n$$$. The numbering is assigned according to the order in which the left brackets appear: the first left bracket that appears and its matching right bracket form bracket pair $$$1$$$, the second left bracket that appears and its matching right bracket form bracket pair $$$2$$$, and so on.

Based on this valid bracket sequence, Fanfan constructs a binary tree according to the following rules:

For the bracket pair numbered $$$p$$$ (whose corresponding bracket positions in the sequence are $$$s_i$$$ and $$$s_j$$$, where $$$s_i$$$ is a left bracket and $$$s_j$$$ is the matching right bracket), we examine $$$s_{i+1}$$$ and $$$s_{j+1}$$$:

If $$$s_{i+1}$$$ is a left bracket, then let the corresponding bracket pair be numbered $$$l$$$, and make $$$l$$$ the left child of $$$p$$$;

If $$$s_{j+1}$$$ is a left bracket, then let the corresponding bracket pair be numbered $$$r$$$, and make $$$r$$$ the right child of $$$p$$$.

Now, Fanfan has lost the original bracket sequence $$$s$$$, but the constructed binary tree structure is still available. Your task is to reconstruct the original valid bracket sequence $$$s$$$ from the given binary tree.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), denoting the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), denoting the number of bracket pairs.

The next $$$n$$$ lines each contain two integers $$$l$$$ and $$$r$$$, representing the left child and right child of each bracket pair numbered from $$$1$$$ to $$$n$$$, respectively. If a bracket pair has no left child or no right child, then the corresponding $$$l$$$ or $$$r$$$ is $$$0$$$.

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

Output

For each test case, output a line containing a string consisting of $$$($$$ and $$$)$$$, representing the reconstructed valid bracket sequence $$$s$$$.

Example
Input
1
3
2 3
0 0
0 0
Output
(())()
Note

The binary tree structure corresponding to the sample input is as follows:

The bracket pair numbered $$$1$$$ has left child $$$2$$$ and right child $$$3$$$;

The bracket pairs numbered $$$2$$$ and $$$3$$$ have no children.

The corresponding valid bracket sequence is $$$(())()$$$, where:

Bracket pair $$$1$$$ consists of the $$$1$$$st character (a left bracket) and the $$$4$$$th character (a right bracket);

Bracket pair $$$2$$$ consists of the $$$2$$$nd character (a left bracket) and the $$$3$$$rd character (a right bracket);

Bracket pair $$$3$$$ consists of the $$$5$$$th character (a left bracket) and the $$$6$$$th character (a right bracket).