Moore Machine

A Moore machine is a finite-state machine whose output is determined by its current state. It is named after the American mathematician and computer scientist Edward F. Moore. The state transitions of a Moore machine are driven by its input. For example, on input aabba a certain Moore machine may output PRETTY.

States are drawn as nodes and transitions as arrows labeled with an input symbol. One state is the start state, and a state N together with its output symbol S is written N/S.

In general a Moore machine may contain cycles, but in this problem we consider only Moore machines with no cycles at all. Such a machine is called a series-parallel Moore machine.

A series-parallel Moore machine can be written compactly as a string:

• A machine with a single state whose output is S is written S (S is an uppercase letter).
• A machine with a single state whose output symbol has been erased is written _.
• Sub-machines M1, M2, …, Mk connected in series are written M1M2…Mk.
• Sub-machines connected in parallel are written M1|M2|…|Mk.
• When a machine is used as part of a larger machine, that part is wrapped in parentheses.

The output of a series connection is the concatenation, in order, of the outputs of its sub-machines. The output of a parallel connection is the output of exactly one of its sub-machines.

Exactly one output symbol of this series-parallel Moore machine has been erased (shown as _). Given the machine expression and the actually observed output string, write a program that recovers the erased symbol.

For example, if the machine is A(B|_)C and the output is ADC, then the middle parallel part must have passed through the erased state rather than B, so the erased symbol is D. If the machine is A(B|D|_)C and the output is ADC, the middle letter D could come either from the D branch or from the erased branch, so the erased symbol cannot be determined uniquely. It is also possible that the observed output is a string the machine can never produce.

Therefore, print the erased symbol if it can be determined uniquely; print _ if it cannot be determined uniquely; and print ! if the given machine cannot produce the observed output.

The first line contains the number of test cases T. Each test case consists of two lines: the first line is the expression of a series-parallel Moore machine, and the second line is the observed output string. All output symbols are uppercase letters. The outermost connection of the machine is always a series, and there is exactly one erased symbol (_). Each line has length at most 100.

For each test case, print the answer on its own line. Print the erased symbol if it can be determined uniquely, _ if it cannot be determined uniquely, or ! if the given machine cannot produce the observed output.