괄호 순서

n 괄호 문자열은 n개의 (와 n개의 )로 이루어진다.

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

인접한 괄호 쌍 ()를 반복해서 지워 빈 문자열로 만드는 방법이 존재한다.

예를 들어, (())는 올바른 괄호 문자열이다. 2nd 위치와 3rd 위치의 쌍을 지우면 ()가 되고, 그다음에는 빈 문자열로 만들 수 있다. )()(는 올바른 괄호 문자열이 아니다. 2nd 위치와 3rd 위치의 쌍을 지우면 )(가 되고, 더 이상 아무것도 지울 수 없다.

이제 모든 올바른 n 괄호 문자열이 있다. 사전순으로 k번째로 작은 문자열을 구하라.

예를 들어, 다음은 올바른 3 괄호 문자열을 모두 사전순으로 나열한 것이다.

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

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ n ≤ 10. 1 ≤ k ≤ 100000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ n ≤ 100. 1 ≤ k ≤ $10^{18}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄은 두 정수 n과 k로 이루어진 하나의 테스트 케이스를 나타낸다. 2

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 모든 올바른 n 괄호 문자열 중 사전순으로 k번째로 작은 괄호 문자열이다. 서로 다른 n 괄호 문자열이 k개보다 적으면 "Doesn't Exist!"를 출력한다.