21615_BracketExpression

A string S that consists of bracket (), [] and {} only is considered to be valid:

(a)  if S is an empty string;

(b)  if both A and B are valid, and S=AB;

(c)  if A is valid, and S = (A);

(d)  if A is valid, and S = [A];

(e)  if A is valid, and S = {A};

Given the length n, we can construct many valid bracket strings. For example, suppose n = 4, then there are 18 valid bracket strings, which are listed in alphabetical order as follows: (()), ()(), ()[], (){}, ([]), ({}), [()], [[]], [](), [][], []{}, [{}], {()}, {[]}, {{}}, {}(), {}[], {}{}.

If we numbered them with integers starting from 0, then string ()[] can be called the 2nd valid bracket string of length 4, and the 14th string is {{}}.

Now, given the length n, and the index k, your task is to find out which the corresponding valid bracket string is in alphabetical order.

Input may contain several test cases. The first line is a positive integer, T ( T ≤ 100 ), the number of test cases below. Each test case contains two integers n, k in a single line, n ( 1 ≤ n ≤ 32, n is even ) is the length of bracket string, and k ( 0 ≤ k ≤ 10¹⁸ ) is the index of the valid bracket string that should be found.

For each test case, if the k-th valid string of length n in alphabetical order exists, just output that string, otherwise, output "invalid" (without quotation mark).

3
2 3
4 2
1 14

invalid
()[]
{{}}