가장 짧은 허용 문자열

이 문제에서는 알파벳 소문자 "a", "b", "c"로 이루어진 문자열을 다룬다.

정규 표현식을 다음과 같이 재귀적으로 정의한다.

1. 한 문자 "$"는 빈 문자열을 허용하는 정규 표현식이다.
2. 한 문자 "a", "b", "c"는 각각 문자열 "a", "b", "c"를 허용하는 정규 표현식이다.
3. $P$가 정규 표현식이면 "( $P$ )"도 정규 표현식이고, $P$가 허용하는 모든 문자열을 허용한다.
4. $P$가 규칙 1--4 중 하나를 적용한 직접 결과인 정규 표현식이면, 그 반복 "$P$ *"도 정규 표현식이고, $k$가 음이 아닌 정수일 때 $s = u_1 u_2 \ldots u_k$ (0개 이상의 문자열을 이어 붙인 것) 꼴의 문자열을 허용한다. 여기서 각 문자열 $u_i$는 $P$가 허용한다.
5. $P$와 $Q$가 규칙 1--5 중 하나를 적용한 직접 결과인 정규 표현식이면, 그 연결 "$P$ {} $Q$"도 정규 표현식이고, $s = u v$ ($u$와 $v$를 이어 붙인 것이며 각각은 빈 문자열일 수 있다) 꼴의 문자열을 허용한다. 여기서 접두사 $u$는 $P$가 허용하고 접미사 $v$는 $Q$가 허용한다.
6. $P$와 $Q$가 규칙 1--6 중 하나를 적용한 직접 결과인 정규 표현식이면, 그 합집합 "$P$ | $Q$"도 정규 표현식이고, $P$가 허용하는 문자열과 $Q$가 허용하는 문자열을 모두 허용한다.

규칙 4--6의 제한은 모호함을 없애고 연산의 우선순위를 정하기 위해 두었다. 정규 표현식을 읽을 때는 반복, 연결, 합집합 순으로 계산한다. 괄호는 안에 묶인 연산의 우선순위를 높이는 통상적인 역할을 한다. 예를 들어 정규 표현식 "a(bac|ac*)"는 "a 다음에 (b 다음에 a 다음에 c) 또는 (a 다음에 c가 0개 이상)"를 허용하는 것으로 읽는다.

정규 표현식 $r$이 주어질 때, 이 정규 표현식 $r$이 허용하는 가장 짧은 문자열 $s$를 구하라. 그러한 문자열이 여러 개라면 사전 순으로 가장 작은 것을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 300$).

다음 $T$개 줄에 각각 하나의 테스트 케이스가 주어진다. 각 테스트 케이스는 위 규칙으로 구성된 문자열인 정규 표현식 $r$ 하나로 이루어진다. 길이는 1자 이상 300자 이하이다.

모든 정규 표현식의 길이 합은 300 이하이다.

각 테스트 케이스마다 주어진 정규 표현식 $r$이 허용하는 가장 짧은 문자열을 한 줄에 출력한다. 그러한 문자열이 여러 개라면 사전 순으로 가장 작은 것을 출력한다.

답이 빈 문자열이면 대신 한 문자 "$"를 출력한다.