Parentheses Order (Small)

A parentheses string of length $2n$ consists of $n$ opening brackets ( and $n$ closing brackets ).

A valid parentheses string is defined like this:

A string you can turn into the empty string by repeatedly erasing an adjacent () pair.

For example, (()) is valid. Erase the pair at positions 2 and 3 to get (), then erase that pair to get the empty string. )()( is not valid. Erasing the pair at positions 2 and 3 leaves )(, and nothing more can be erased.

Collect every valid parentheses string with $n$ opening and $n$ closing brackets, sort them in lexicographic order, and find the $k$-th one. In this comparison ( comes before ).

For $n = 3$ the valid parentheses strings in lexicographic order are:

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

The first line has the number of test cases $T$. Each of the next $T$ lines has two integers $n$ and $k$ separated by a space.

For each test case print one line in the form Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the string that comes $k$-th in lexicographic order among the valid parentheses strings with $n$ opening and $n$ closing brackets. If fewer than $k$ such strings exist, print Doesn't Exist! in place of $y$.

• $1 \le T \le 100$
• $1 \le n \le 10$
• $1 \le k \le 100000$