시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 231 16 14 19.178%

문제

무어 기계는 상태에 의해서 출력이 결정되는 유한 상태 기계이다. 무어 기계는 이름은 미국의 수학자이자 컴퓨터 과학자 Edward F. Moore의 이름을 따서 지었다. 무어 기계의 상태 전이는 입력에 의해서 정해진다. 예를 들어, 입력이 "aabba"이면, 아래와 같은 무어 기계의 출력은 "PRETTY"가 된다.

위의 그림에서 동그라미는 상태를 나타내고, 화살표 위의 글자는 입력 심볼을 나타낸다. 상태 중 하나는 시작 상태로 디자인 되어져 있다. 이 상태는 출발 노드가 없는 화살표로 나타나 있다. 이 경우에 시작 상태는 1번 상태이다. 상태 N과 출력 심볼 S는 N/S로 나타낸다.

대부분 경우에 무어 기계는 사이클을 가진다. 이 문제에서는 사이클이 전혀 없는 무어 기계를 다루며, 이런 종류의 기계를 직병렬 무어 기계라고 한다.

직병렬 무어 기계의 한 출력 심볼이 지워져 있다. 기계의 출력이 주어졌을 때, 지워진 심볼을 찾는 프로그램을 작성하시오. 항상 지워진 심볼을 찾을 수 있는 것은 아니다.

예를 들어, 아래 그림과 같은 직병렬 무어 기계가 있다.

위의 그림에는 상태를 간단하게 나타내기 위해 출력 심볼만 나타나 있다. 빈 원은 출력 심볼이 지워진 상태이다. 예를 들어, 기계의 출력이 "ADC"인 경우에는, 지워진 심볼이 D임을 알 수 있다. 하지만, 출력이 "ABC" 라면, 주어진 심볼을 유일하게 결정할 수 없다. "ABD"는 이 기계에서 나올 수 없는 출력이기 때문에, 불가능한 경우이다.

직병렬 무어 기계는 직병렬 그래프로 나타낼 수 있고, 간단히 표현할 수 있다. 상태가 하나이고, 출력이 S인 무어 기계는 'S' 로 나타낸다. 상태가 하나이고, 출력 심볼이 지워진 무어 기계는 '_'로 나타낸다. 여러 개의 부분 기계 M1, M2, ..., Mk가 직렬로 연결된 무어 기계는 M1M2...Mk로 나타낸다. 또, 부분 기계가 병렬로 연결된 무어 기계는 M1|M2|...|Mk로 나타낸다. 한 무어 기계가 더 큰 무어 기계의 일부로 사용된다면, 그 부분을 괄호로 감싼다. 이 방법을 사용하면, 위의 무어 기계는 A(B|_)C로 나타낼 수 있다.

직병렬 무어 기계와 그 기계의 출력이 주어졌을 때, 지워진 심볼을 구하는 프로그램을 작성하시오. 만약, 지워진 심볼을 유일하게 결정할 수 없다면, '_'를 출력한다. 또, 기계에서 나올 수 없는 출력이 주어진 경우에는 '!'를 출력한다.

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 직병렬 무어 기계가 주어지고, 둘째 줄에는 기계의 출력이 주어진다. 출력 심볼은 알파벳 대문자로만 이루어져 있다. 무어 기계의 가장 바깥쪽 연결은 직렬이다. 또, 지워진 심볼의 개수는 하나이다. 각 줄의 길이는 100보다 작거나 같다.

출력

각 테스트 케이스마다, 지워진 심볼을 출력한다. 만약, 유일하게 결정할 수 없다면 '_'를 출력한다. 또, 입력으로 주어진 기계에서 만들 수 없는 경우에는 '!'를 출력한다.

예제 입력

3
A(B|_)C
ADC
A(B|D|_)C
ADC
A(B|CD(E|_)G)E
BOY

예제 출력

D
_
!

힌트