이항 연산자

음이 아닌 정수, 괄호 (), 덧셈 +, 곱셈 *, 그리고 추가 연산자 #를 사용하는 유효한 산술식의 목록이 주어진다. 식은 완전히 괄호로 묶여 있으며 중위 표기법으로 작성되어 있다.

완전히 괄호로 묶인 식이란 모든 연산자와 그 피연산자가 하나의 괄호로 묶인 식이다. 예를 들어 식 $x+y$는 완전히 괄호로 묶으면 $(x+y)$가 되고, $x+y+z$는 $((x+y)+z)$가 된다. 하지만 $0$은 하나의 숫자로만 이루어져 있고 연산자가 없으므로, 완전히 괄호로 묶어도 여전히 $0$이다. $((x+y))$에는 불필요한 괄호가 있으므로 완전히 괄호로 묶인 것으로 간주하지 않는다.

연산자 +와 *는 각각 덧셈과 곱셈을 나타내며, #는 임의의 전역 함수일 수 있다.

식들을 동치류로 분류하려 한다. 두 식은 #가 어떤 함수를 나타내는지와 관계없이 반드시 같은 수치가 나올 때, 그리고 그럴 때에만 같은 동치류에 속한다.

주어진 하나의 테스트 케이스에 포함된 모든 식에서 #는 같은 함수를 나타낸다고 가정할 수 있다. 즉, #가 덧셈이나 뺄셈처럼 알려진 어떤 함수를 나타낼 수는 있지만, 같은 테스트 케이스의 서로 다른 부분에서 두 함수를 모두 나타낼 수는 없다.

예를 들어 다음 식들을 살펴보자: $F_1$=((1#(1+1))+((2#3)*2)) $F_2$=(((2#3)+(1#2))+(2#3)) $F_3$=((2*(2#3))+(1#2)).

A = 1#2라 하고, B = 2#3라 하자. 그러면 식들을 다음과 같이 다시 쓸 수 있으므로, #가 나타내는 함수와 관계없이 $F_1$=$F_2$=$F_3$라고 할 수 있다: $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).

하지만 식 $F_4$=((0#0)+(0#0))와 $F_5$=(0#0)를 살펴보자. #가 덧셈을 나타낸다면 $F_4=F_5$이다. 하지만 #가 $f(x,y)=C$이고 $C$가 0이 아닌 정수가 되도록 한다면, $2C \neq C$이므로 $F_4 \neq F_5$이다. 따라서 $F_4$와 $F_5$는 같은 동치류에 속하지 않는다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$ $1 \le \mathbf{N} \le 100$ 모든 $i$에 대해 $\mathbf{E_i}$의 길이는 최대 $100$이다. 모든 $i$에 대해 $\mathbf{E_i}$는 유효하다.

Test Set 1

각 식에는 #가 최대 하나 있다.

Test Set 2

추가 제약 조건은 없다.

입력의 첫째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 $\mathbf{N}$가 포함된 한 줄로 시작한다. 이어서 $\mathbf{N}$개의 줄이 주어진다. $i$번째 줄에는 식 하나인 $\mathbf{E_i}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $Y_1, Y_2, \dots, Y_\mathbf{N}$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $Y_i$는 아래 조건을 만족하는 사전순으로 가장 작은 수열이다:

• $1 \le Y_i \le Z$. 여기서 $Z$는 주어진 테스트 케이스의 전체 동치류 수를 나타낸다.

• $\mathbf{E_i}$와 $\mathbf{E_j}$가 같은 동치류에 속할 때, 그리고 그럴 때에만 $Y_i = Y_j$이다.

이 예제 테스트 세트에는 $3$개의 테스트 케이스가 포함되어 있다.

테스트 케이스 1에는 $7$개의 식과 총 $2$개의 동치류가 있으며, 이 동치류들은 $G_1$와 $G_2$로 표시된다. $\mathbf{E_1}$=(1*(1#2)), $\mathbf{E_2}$=(0*(1#2)), $\dots$, $\mathbf{E_7}$=(((1+(1#2))+3)*0). $\mathbf{E_1}$, $\mathbf{E_3}$, $\mathbf{E_6}$은 $G_1$에 속하고, $\mathbf{E_2}$, $\mathbf{E_4}$, $\mathbf{E_5}$, $\mathbf{E_7}$는 $G_2$에 속한다. 테스트 케이스 1에서 동치류에 관한 요구 사항을 만족하는 $Y_i$의 수열은 $2$개이며, 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$로 표시된다. $\mathbf{E_1}$, $\mathbf{E_2}$, $\mathbf{E_4}$는 $G_1$에 속하고, $\mathbf{E_3}$와 $\mathbf{E_5}$는 $G_2$에 속한다. 따라서 테스트 케이스 2의 출력은 다음과 같다: Case #2: 1 1 2 1 2.

테스트 케이스 3에는 어떤 #도 포함하지 않는 식이 $2$개 있다. 이 두 식은 같은 값으로 계산되므로 같은 동치류에 속한다.

Additional Sample - Test Set 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는 주어진 입력의 동치류에 관한 요구 사항을 만족하는 다른 여러 수열 중 하나이지만, 이 수열은 사전순으로 가장 작은 수열이 아니므로 올바른 답이 아니라는 점에 유의하라.