Description

简要题意：给定一个数字字符串 $\mathbf{S}$，在其中插入最少数量的左右括号，使得生成的字符串是平衡的，并且每个数字 $d$ 恰好位于 $d$ 对匹配的括号内。

我们定义字符串中两个括号的嵌套为它们之间严格包含的子串。一个左括号和其右侧的一个右括号称为匹配，如果它们的嵌套为空，或者它们的嵌套中的每个括号都与另一个括号匹配。位置 $p$ 的嵌套深度是包含 $p$ 的匹配括号对的数量 $m$。

例如，在以下字符串中，所有数字都与其嵌套深度匹配：0((2)1)、(((3))1(2))、((((4))))、((2))((2))(1)。前三个字符串在保持数字顺序相同的情况下长度最短，但最后一个不是，因为 ((22)1) 也包含数字 221 且更短。

给定一个数字字符串 $\mathbf{S}$，找到另一个由括号和数字组成的字符串 $\mathbf{S}'$，满足以下条件：

• $\mathbf{S}'$ 中的所有括号都与其他括号匹配；
• 从 $\mathbf{S}'$ 中移除所有括号后得到 $\mathbf{S}$；
• $\mathbf{S}'$ 中的每个数字等于其嵌套深度；
• $\mathbf{S}'$ 的长度最短。

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 行，每行表示一个测试用例，仅包含字符串 $\mathbf{S}$。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是上述定义的字符串 $\mathbf{S}'$。

4
0000
101
111000
1

Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)

Hint

样例解释

字符串 ()0000()、(1)0(((()))1) 和 (1)(11)000 分别不是样例 #1、#2 和 #3 的有效解，因为它们不是最短的。此外，1)( 和 )(1 不是样例 #4 的有效解，因为它们包含未匹配的括号，且在数字 1 的位置嵌套深度为 0。

你可以通过移除题目描述中提到的示例字符串的括号来创建仅适用于测试集 2 的样例输入。

数据范围

• $1 \leq \mathbf{T} \leq 100$；
• $1 \leq \mathbf{S}$ 的长度 $\leq 100$。

测试集 1（5 分，可见判定）

• $\mathbf{S}$ 中的每个字符为 0 或 1。

测试集 2（11 分，可见判定）

• $\mathbf{S}$ 中的每个字符为 0 到 9 的数字（含）。

翻译由 DeepSeek V3 完成