시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB39121230.769%

문제

An n parentheses sequence consists of n (s and n )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 2nd and 3rd position and it becomes () then you can make it empty. )()( is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes )( and you cannot erase any more.

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

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

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

입력

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

출력

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

제한

  • 1 ≤ T ≤ 100.
  • 1 ≤ n ≤ 100.
  • 1 ≤ k ≤ 1018.

예제 입력 1

3
2 2
3 4
3 6

예제 출력 1

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.