题目描述

一个长度为 $n$ 的括号序列由 $n$ 个 ( 和 $n$ 个 ) 组成。

一个合法的括号序列定义如下：

你可以找到一种方式，通过反复删除相邻的括号对 () 使得序列最终变为空。

例如，( ( ) ) 是一个合法的括号序列：你可以删除第 $2$ 和第 $3$ 个位置上的括号对，得到 ()，然后再将其清空。

) ( ) ( 不是一个合法的括号序列：删除第 $2$ 和第 $3$ 个位置上的括号对后，得到 ) (，此后无法再删除任何括号对。

现在，我们有所有长度为 $n$ 的合法括号序列。请找出其中字典序第 $\mathbf{k}$ 小的序列。

例如，以下是长度为 $3$ 的所有合法括号序列，按字典序排列：

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

输入格式

输入的第一行给出测试用例的数量 $T$。接下来 $T$ 行，每行对应一个测试用例，包含两个整数 $n$ 和 $k$。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有长度为 $n$ 的合法括号序列中字典序第 $\mathbf{k}$ 小的序列。如果不同的长度为 $n$ 的合法括号序列不足 $\mathbf{k}$ 个，则输出 Doesn't Exist!。

3
2 2
3 4
3 6

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

提示

限制

$1 \le T \le 100$。

小数据集（测试集 1 - 可见）

$1 \le n \le 10$。

$1 \le k \le 100000$。

大数据集（测试集 2 - 隐藏）

$1 \le n \le 100$。

$1 \le k \le 10^{18}$。

翻译由 DeepSeek V4 Pro 完成