이항 연산자

음이 아닌 정수, 괄호 (), 덧셈 +, 곱셈 *, 그리고 추가 연산자 #로 이루어진 올바른 산술 표현식의 목록이 주어진다. 표현식은 완전히 괄호로 묶여 있고 중위 표기법을 따른다.

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

연산자 +와 *는 덧셈과 곱셈을 나타내며, #는 어떤 전함수든 될 수 있다.

표현식들을 동치류로 분류하려고 한다. 두 표현식이 #가 어떤 함수를 나타내든 항상 같은 숫자 값을 내는 경우, 그리고 그런 경우에만 두 표현식은 같은 동치류에 속한다.

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

예를 들어 다음 표현식들을 보자.

• F1=((1#(1+1))+((2#3)*2))
• F2=(((2#3)+(1#2))+(2#3))
• F3=((2*(2#3))+(1#2))

A = 1#2, B = 2#3이라 하자. 그러면 #가 어떤 함수를 나타내든 F1=F2=F3이다. 표현식을 다음과 같이 다시 쓸 수 있기 때문이다.

• F1=((1#2)+((2#3)*2))=(A+(B*2))=(A+2B)
• F2=(((2#3)+(2#3))+(1#2))=((B+B)+A)=(A+2B)
• F3=((2*(2#3))+(1#2))=((2*B)+A)=(A+2B)

그러나 F4=((0#0)+(0#0))와 F5=(0#0)을 보자. #가 덧셈을 나타내면 F4=F5이다. 하지만 #가 $C$가 0이 아닌 정수인 f(x,y)=C라면 2C≠C이므로 F4≠F5이다. 따라서 F4와 F5는 같은 동치류에 속하지 않는다.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. $T$개의 테스트 케이스가 이어진다. 각 테스트 케이스는 정수 $N$이 있는 줄로 시작한다. 다음 $N$개의 줄이 이어지며, $i$번째 줄에는 표현식 Ei가 하나 주어진다.

각 테스트 케이스마다 Case #x: Y1,Y2,…,YN을 한 줄에 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $Y\_i$는 다음 조건을 만족하는 사전순으로 가장 작은 수열이다.

1. $1 \le Y\_i \le Z$이며, $Z$는 해당 테스트 케이스의 전체 동치류 수이다.
2. $E\_i$와 $E\_j$가 같은 동치류에 속하는 경우, 그리고 그런 경우에만 $Y\_i=Y\_j$이다.

• $1 \le T \le 100$
• $1 \le N \le 100$
• 모든 $i$에 대해 $E\_i$의 길이는 100 이하이다.
• 모든 $i$에 대해 $E\_i$는 올바른 표현식이다.