공통 부분식 제거

집합 $\Sigma$는 a, b, f, aa, fun, kvqf처럼 소문자 1개에서 4개로 이루어진 모든 단어의 집합이다. 임의의 기호 $f \in \Sigma$에 대해, 다음 두 규칙으로 식을 만든다.

• $E \rightarrow f$
• $E \rightarrow f(E,E)$

모든 식은 그 구문 구조를 그대로 나타내는 트리에 대응된다. 예를 들어 식

a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))

은 노드가 $21$개인 트리에 대응된다.

트리 대신 그래프(방향 비순환 그래프)를 사용하면 같은 부분식을 한 번만 저장하고 공유할 수 있어 표현의 크기를 줄일 수 있다. 위 식은 노드가 단 $7$개인 그래프로 나타낼 수 있다.

트리 자체도 하나의 그래프이므로 그래프 표현은 유일하지 않다. 주어진 식에 대해, 가능한 한 적은 노드로 그 식을 나타내는 그래프를 구하여라.

첫째 줄에 식의 개수 $c$ ($1 \le c \le 200$)가 주어진다. 이어지는 $c$개의 줄에는 각각 위 문법을 따르는 식이 공백 없이 하나씩 주어진다. 각 식의 트리 표현은 최대 $50000$개의 노드를 가진다.

각 식에 대해, 가능한 한 적은 노드를 사용하는 그래프 표현을 한 줄에 하나씩 출력한다.

그래프 표현은 반복되는 부분식을 숫자로 대체하여 문자열로 적는다. 각 숫자는 그 위치에 넣어야 할 부분식의 루트 노드를 가리킨다. 노드는 처음 적히는 순서대로 $1$부터 차례로 번호를 매기며, 이 번호는 그래프에 실제로 나타나는 노드만 세고 숫자로 대체된 자리는 세지 않는다. 숫자는 앞서 이미 적은 노드만 가리킬 수 있으므로, 앞을 가리키는 참조는 존재하지 않는다.

예시 식 a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))의 답은 a(b(f(a,4),b(3,f)),f(2,6))이다.