Parentheses Order (Large)

An n pair parentheses sequence is a string of length 2n made of n opening brackets ( and n closing brackets ).

A valid parentheses sequence is defined as follows.

You can repeat erasing an adjacent pair () until the string becomes empty.

For example, (()) is valid. Erase the characters at positions 2 and 3 to get (), then erase that pair to get the empty string. )()( is not valid. After erasing the characters at positions 2 and 3 you are left with )(, and nothing more can be erased.

Collect every valid n pair parentheses sequence and sort them in lexicographic order, then find the k-th one. In the comparison ( comes before ).

For n equal to 3, the valid sequences in lexicographic order are:

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

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

For each test case print one line of the form Case #x: y. Here x is the test case number starting from 1, and y is the k-th sequence in lexicographic order among all valid n pair parentheses sequences. If fewer than k such sequences exist, print Doesn't Exist! in place of y.

• $1 \le T \le 100$
• $1 \le n \le 100$
• $1 \le k \le 10^{18}$