괄호 문자열 순서 (라지)

n쌍 괄호 문자열은 여는 괄호 ( n개와 닫는 괄호 ) n개로 이루어진 길이 2n짜리 문자열이다.

올바른 괄호 문자열은 다음과 같이 정의한다.

서로 붙어 있는 () 한 쌍을 지우는 작업을 반복해서 빈 문자열로 만들 수 있으면 올바른 괄호 문자열이다.

예를 들어 (())는 올바른 괄호 문자열이다. 2번째와 3번째 문자를 지우면 ()가 되고, 한 번 더 지우면 빈 문자열이 된다. )()(는 올바르지 않다. 2번째와 3번째 문자를 지우면 )(가 남고 더는 지울 수 없다.

n쌍 올바른 괄호 문자열을 모두 모아 사전순으로 정렬했을 때 k번째 문자열을 구하여라. 사전순 비교에서 (는 )보다 앞선다.

예를 들어 n이 3일 때 올바른 괄호 문자열을 사전순으로 나열하면 다음과 같다.

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

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에 각각 두 정수 n과 k가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 n쌍 올바른 괄호 문자열을 사전순으로 정렬했을 때의 k번째 문자열이다. 올바른 괄호 문자열이 k개보다 적으면 y 자리에 Doesn't Exist!를 출력한다.

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