题目描述

给定一个使用非负整数、括号 $()$、加号 $+$、乘号 $*$ 以及一个额外运算符 $\#$ 组成的合法算术表达式列表。这些表达式是完全括号化的，并且采用中缀表示法。

完全括号化的表达式是指每个运算符及其操作数都被包裹在一对括号中。

例如，表达式 $x+y$ 完全括号化后变为 $(x+y)$，而 $x+y+z$ 完全括号化后变为 $((x+y)+z)$。然而，$0$ 仍然是 $0$，因为它只包含一个数字而没有运算符。$((x+y))$ 不被认为是完全括号化的，因为它有多余的括号。

运算符 $+$ 和 $*$ 分别表示加法和乘法，而 $\#$ 可以是任意一个全函数（total function）。

你想将这些表达式分组为等价类，其中两个表达式属于同一个等价类当且仅当无论 $\#$ 代表哪个函数，它们的结果数值总是相同。

你可以假设在同一个测试用例中，$\#$ 代表同一个函数。这意味着 $\#$ 可能代表某个已知函数（如加法或减法），但在同一个测试用例的不同部分不会代表不同的函数。

例如，考虑以下表达式：

$$\begin{aligned} F_1&=((1\#(1+1))+((2\#3)*2))\\ F_2&=(((2\#3)+(1\#2))+(2\#3))\\ F_3&=((2*(2\#3))+(1\#2)) \end{aligned}$$

令 $A=1\#2$，$B=2\#3$，则无论 $\#$ 代表什么函数，我们都可以将表达式重写为：

$$\begin{aligned} F_1&=((1\#2)+((2\#3)*2))=(A+(B*2))=(A+2B)\\ F_2&=(((2\#3)+(2\#3))+(1\#2))=((B+B)+A)=(A+2B)\\ F_3&=((2*(2\#3))+(1\#2))=((2*B)+A)=(A+2B) \end{aligned}$$

因此 $F_1=F_2=F_3$。

然而，考虑表达式 $F_4=((0\#0)+(0\#0))$ 和 $F_5=(0\#0)$。如果 $\#$ 表示加法，那么 $F_4=F_5$。但是，如果 $\#$ 是常数函数 $f(x,y)=C$（$C$ 为非零整数），则 $F_4 \ne F_5$，因为 $2C \ne C$。因此 $F_4$ 和 $F_5$ 不属于同一个等价类。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。随后 $N$ 行，第 $i$ 行包含一个表达式 $E_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: Y1 Y2 ... YN，其中 $x$ 是测试用例编号（从 $1$ 开始），$Y_i$ 是满足以下条件的字典序最小的序列：

1. $1 \le Y_i \le Z$，其中 $Z$ 表示该测试用例中等价类的总数。
2. $Y_i = Y_j$ 当且仅当 $E_i$ 和 $E_j$ 属于同一个等价类。

3
7
(1*(1#2))
(0*(1#2))
(1#2)
0
(3*0)
((1#2)*1)
(((1+(1#2))+3)*0)
5
(1*((1+(2#2))+3))
((0+(2#2))+4)
(100#2)
(((1+(2#2))+3)*1)
((50*2)#2)
2
(9999999999999999999999999999999999999999+1)
(100000000000000000000*100000000000000000000)

Case #1: 1 2 1 2 2 1 2
Case #2: 1 1 2 1 2
Case #3: 1 1

1
9
((2*(2#3))+(1#2))
(0*(1#2))
0
((1#(1+1))+((2#3)*2))
(3*0)
(1#(2#3))
(((2#3)+(1#2))+(2#3))
(4#7)
(7#4)

Case #1: 1 2 2 1 2 3 1 4 5

提示

这个样例测试集 $1$ 包含 $3$ 个测试用例。

测试用例 $1$ 有 $7$ 个表达式，共 $2$ 个等价类，记作 $G_1$ 和 $G_2$。

$E_1=(1*(1\#2))$，$E_2=(0*(1\#2))$，$\ldots$，$E_7=(((1+(1\#2))+3)*0)$。

$E_1$、$E_3$ 和 $E_6$ 属于 $G_1$，$E_2$、$E_4$、$E_5$ 和 $E_7$ 属于 $G_2$。

在测试用例 $1$ 中，有 $2$ 个序列 $Y_i$ 满足等价类的要求：$2\ 1\ 2\ 1\ 1\ 2\ 1$ 和 $1\ 2\ 1\ 2\ 2\ 1\ 2$。

由于 $1\ 2\ 1\ 2\ 2\ 1\ 2$ 字典序更小，因此测试用例 $1$ 的输出为：Case #1: 1 2 1 2 2 1 2。

测试用例 $2$ 有 $5$ 个表达式，共 $2$ 个等价类，记作 $G_1$ 和 $G_2$。

$E_1$、$E_2$ 和 $E_4$ 属于 $G_1$，$E_3$ 和 $E_5$ 属于 $G_2$。

因此，测试用例 $2$ 的输出为：Case #2: 1 1 2 1 2。

测试用例 $3$ 有 $2$ 个表达式，它们都不包含 $\#$。

这两个表达式的计算结果相同，因此属于同一个等价类。

在所提供的样例 $2$ 中，共有 $5$ 个等价类。输入中的第一个表达式为 $((2*(2\#3))+(1\#2))$。与其属于同一等价类的所有表达式在输出中用 $1$ 表示。用 $2$ 表示的等价类包含 $(0*(1\#2))$、$0$ 和 $(3*0)$。用 $3$ 表示的等价类包含 $(1\#(2\#3))$。最后两个表达式 $(4\#7)$ 和 $(7\#4)$ 彼此不等价，也与之前的任何表达式不等价。注意，$2\ 1\ 1\ 2\ 1\ 3\ 2\ 5\ 4$ 是满足给定输入等价类要求的众多序列之一，但它不是正确答案，因为该序列不是字典序最小的。

限制条件

$1 \le T \le 100$

$1 \le N \le 100$

对于所有 $i$，$E_i$ 的长度至多为 $100$。

对于所有 $i$，$E_i$ 是合法的。

测试集 1

每个表达式中最多有一个 $\#$。

测试集 2

无额外限制。

翻译由 DeepSeek V4 Pro 完成