简而言之：给定一个数字字符串 $S$，在其中插入最少数量的左括号和右括号，使得结果字符串是平衡的，且每个数字 $d$ 都恰好位于 $d$ 对匹配的括号内。

字符串中两个括号的“嵌套”（nesting）是指严格位于它们之间的子串。如果一个左括号和一个位于其右侧的右括号的嵌套为空，或者其嵌套中的每个括号都能与嵌套内的另一个括号匹配，则称这两个括号匹配。位置 $p$ 的“嵌套深度”（nesting depth）是指包含 $p$ 的匹配括号对的数量。

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

给定一个数字字符串 $S$，找到另一个由括号和数字组成的字符串 $S'$，使得：

• $S'$ 中的所有括号都与另一个括号匹配，
• 从 $S'$ 中删除所有括号后得到 $S$，
• $S'$ 中的每个数字都等于其嵌套深度，且
• $S'$ 的长度最小。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行代表一个测试用例，仅包含字符串 $S$。

输出格式

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

数据范围

$1 \le T \le 100$。 $1 \le \text{length of } S \le 100$。

测试集 1（可见判定） $S$ 中的每个字符要么是 $0$，要么是 $1$。

测试集 2（可见判定） $S$ 中的每个字符都是 $0$ 到 $9$ 之间的十进制数字（包含 $0$ 和 $9$）。

样例

样例输入 1

4
0000
101
111000
1

样例输出 1

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

说明

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

你可以通过删除问题描述中提到的示例字符串中的括号，来创建仅对测试集 2 有效的样例输入。