Brackets

Time limit1sMemory limit512 MB

Summary

For each N, find the valid bracket string with bracket value N whose digit-encoded decimal value is smallest, and print it.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Combinatorics, Math
Solved: No attempts yet

Problem

For a valid bracket string W made of the six characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’, a function val(W) is defined that assigns it an integer ‘bracket value’. First let us define a valid bracket string.

A length-2 string made of a single pair of brackets, namely ‘()’, ‘[]’, ‘{}’, is a valid bracket string. These are called unit brackets. If X and Y are valid bracket strings, then any new string obtained by the following operations is also a valid bracket string.

XY // concatenation of two valid bracket strings.
(X), {X}, [X] // wrapping a whole valid bracket string in brackets again.

Examples of valid and invalid bracket strings follow. There are no spaces between bracket characters.

Valid examples: ({}{}[(())]), (()), {}[][(())]
Invalid examples: {[(())], (([)])), {{{}}(), )]{}

Now we explain how to compute the bracket value val(). The bracket values of the three kinds of unit brackets (), {}, [] are defined as 1, 2, 3 respectively. That is, if the strings are X=‘()’, Y=‘{}’, Z=‘[]’, then val(X) = 1, val(Y) = 2, val(Z) = 3. If X and Y are valid strings, the bracket value of the string Z=XY obtained by concatenating them in order is computed as follows.

val(Z) = val(X) + val(Y)

If a valid string X is wrapped by (), {}, [] as in A=‘(X)’, B=‘{X}’, C=‘[X]’, the bracket values of A, B, C are computed as follows.

val(A) = 2·val(X), val(B) = 3·val(X), val(C) = 5·val(X)

A string with bracket value k is not unique. For example, ‘[]’, ‘{}()’, ‘()()()’ all have bracket value 3. The following table shows examples of the bracket value val(X) corresponding to valid bracket strings.

valid bracket string `X`	val(`X`)
`(()())`	2(1+1) = 4
`[[[]]]`	3×5×5 = 75
`[][][]{()}`	3+3+3+3(1) = 12
`((())[{}])()`	2(2+5×2)+1 = 25

A valid bracket string X can also be expressed as a number. To turn a bracket string into a number, replace each bracket character with a digit from 1 to 6 as in the table below and read the result as a decimal number.

character	`(`	`)`	`{`	`}`	`[`	`]`
digit	1	2	3	4	5	6

The value obtained by converting a bracket string X as described above is denoted dmap(X). The table below shows dmap(X) for some valid bracket strings X.

val(`R`)=3 strings	dmap(`R`)
`()()()`	121212
`{}()`	3412
`(){}`	1234
`[]`	56
val(`R`)=4 strings	dmap(`R`)
`({})`	1342
`()()()()`	12121212
`()[]`	1256
`{}{}`	3434

For a given integer N, you must find and print the valid bracket string X with val(X) = N that has the smallest dmap(X) value. The output string must consist only of bracket characters with no spaces.

Input

The first line gives the number of test cases T. (1 ≤ T ≤ 100) From the second line to the (T+1)-th line, one integer N is given per line. (5 ≤ N ≤ 1,000)

Output

For each test case, find the valid bracket string X with val(X) = N that has the smallest dmap(X) and print it on its own line with no spaces.

Examples2

Example 1
Input
```
1
5
```
Expected output
```
{}[]
```
Example 2
Input
```
3
11
22
33
```
Expected output
```
()[{}]
(()[{}])
([[]])[]
```