Signals

Consider DC (direct current) circuits. Each DC circuit produces a set of output signals. A circuit is made of devices wired together in parallel or in series, and it never contains a feedback loop. Every device emits one specific signal, and the set of output signals of a circuit is fixed by which devices it contains and how they are connected.

For example, take two circuits C1 and C2:

C1 can generate the two signals abc and adc. For a circuit C, its output OUT(C) is the set of every signal it can generate, so OUT(C1) = {abc, adc}. Here OUT(C2) is also {abc, adc}, therefore OUT(C1) = OUT(C2).

There is a special device called the pass device, written 1, that emits no signal at all (it contributes the empty signal). Parallel and serial connections of sub-circuits may be nested and combined freely. For example, take C3 and C4:

Then OUT(C3) = {abc, ac} and OUT(C4) = {abc, aabc, aadc}.

A circuit is written as a string:

• A normal device is written as the lowercase letter that names its signal.
• The pass device is written as 1.
• The parallel connection of two circuits C and D is written C|D.
• The serial connection of C and D (C followed by D) is written by placing them next to each other: CD.
• Parentheses may be used wherever needed to make the connection topology clear. No spaces are allowed inside a circuit description.

The strings that denote the circuits above are:

A sub-circuit may carry redundant parentheses. For instance, C1 may be written (a((b)|((d)))c) instead of a(b|d)c; both denote the same circuit.

Given two circuits C and D, print a single character that describes how their outputs are related, using this table:

Assume that every circuit generates at least one signal; that is, no circuit has the empty output set {}. Nested pass-only circuits such as 1 or (1|1) are still allowed, because their output is the set containing just the empty signal, which is different from the empty set.

The first line contains the number of test cases T (T < 30). Each of the next T lines contains one test case: two circuit descriptions separated by one or more spaces. Each circuit description is shorter than 50 characters.

For each test case, print on its own line the single character (=, <, >, 0, or 1) that describes the relation between the two circuits C and D, in the order they were given. The number of output lines equals the number of test cases.