Bracket String Notation (Small)

Interview

Time limit1.5sMemory limit1024 MB

Summary

Given N, find the shortest bracket string whose value is N, breaking length ties by lexicographic order.

Level: Medium5 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

A bracket string is a string that can be built only with these three rules.

The empty string is a bracket string.
For a bracket string $a$ , ( $a$ ) is a bracket string.
For two bracket strings $a$ and $b$ , $ab$ is a bracket string.

Examples of bracket strings include (())(), (((()())())()), and ((()())()()())(()).

The value of a bracket string is determined as follows.

The value of the empty string is 1.
If the value of a bracket string $a$ is $x$ , then the value of ( $a$ ) is $x + 1$ .
If the values of two bracket strings $a$ and $b$ are $x$ and $y$ , respectively, then the value of $ab$ is $x \times y$ .

For example, (())() represents 6.

() represents $1 + 1 = 2$ .
(()) represents $2 + 1 = 3$ .
(())() represents $3 \times 2 = 6$ .

Given a natural number $N$ , find the shortest bracket string that represents $N$ . If several such strings exist, find the one that comes first in lexicographic order.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 20$ )

From the second line on, each line contains one natural number $N$ . ( $2 \le N \le 1{,}000{,}000$ )

Output

For each test case, print on its own line the shortest bracket string that represents $N$ . If several such strings exist, print the one that comes first in lexicographic order.

Examples2

Example 1

Input

Expected output

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

Example 2

Input

Expected output

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