#216528. [GKS 2014 #B] Parentheses Order

An parentheses sequence consists of ( s and ) s.

A valid parentheses sequence is defined as the following:

You can find a way to repeat erasing adjacent pair of parentheses () until it becomes empty.

For example, ( ( ) ) is a valid parentheses, you can erase the pair on the nd and rd position and it becomes () then you can make it empty.

) ( ) ( is not a valid parentheses, after you erase the pair on the nd and rd position, it becomes ) ( and you cannot erase any more.

Now, we have all valid parentheses sequences. Find the -th smallest sequence in lexicographical order.

For example, here are all valid parentheses sequences in lexicographical order:

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

The first line of the input gives the number of test cases, . lines follow. Each line represents a test case consisting of integers, and .

For each test case, output one line containing "Case #x: y", where is the test case number (starting from 1) and is the -th smallest parentheses sequence in all valid parentheses sequences. Output "Doesn't Exist!" when there are less than different parentheses sequences.

样例输入 1

3
2 2
3 4
3 6

样例输出 1

Case #1: ()()
Case #2: ()(())
Case #3: Doesn't Exist!

Limits

.

Small dataset (Test set 1 - Visible)

.

.

Large dataset (Test set 2 - Hidden)

.

.