신호

직류(DC) 회로가 주어진다. 각 직류 회로는 출력 신호들의 집합을 만들어 낸다. 회로는 여러 소자(device)를 병렬 또는 직렬로 연결해 구성하며, 되먹임(피드백) 회로는 존재하지 않는다. 각 소자는 정해진 신호 하나를 내보내고, 회로의 출력 신호 집합은 어떤 소자를 쓰는지와 그 소자들을 어떻게 연결했는지에 따라 결정된다.

예를 들어 두 회로 C1, C2를 보자.

C1은 abc와 adc 두 신호를 만들 수 있다. 회로 C에 대해 그 출력 OUT(C)는 C가 만들 수 있는 모든 신호의 집합으로 정의한다. 따라서 OUT(C1) = {abc, adc}이다. 여기서 OUT(C2)도 {abc, adc}이므로 OUT(C1) = OUT(C2)이다.

아무 신호도 내보내지 않는 특수한 소자가 있는데, 이를 통과 소자(pass device)라 하고 1로 표기한다(빈 신호를 기여한다). 부분 회로들의 병렬 연결과 직렬 연결은 자유롭게 중첩하고 조합할 수 있다. 예를 들어 C3, C4를 보자.

이때 OUT(C3) = {abc, ac}이고 OUT(C4) = {abc, aabc, aadc}이다.

회로는 다음과 같이 문자열로 표기한다.

• 일반 소자는 그 소자가 내는 신호를 나타내는 소문자로 적는다.
• 통과 소자는 1로 적는다.
• 두 회로 C와 D의 병렬 연결은 C|D로 적는다.
• 두 회로 C와 D를 이어 붙인 직렬 연결(C 다음에 D)은 둘을 나란히 써서 CD로 적는다.
• 연결 구조를 분명히 하기 위해 필요한 곳에 괄호를 쓸 수 있다. 회로 표기 안에는 공백을 넣을 수 없다.

위 회로들을 나타내는 문자열은 다음과 같다.

부분 회로 표기에는 불필요한(중복된) 괄호가 붙을 수 있다. 예를 들어 C1은 a(b|d)c 대신 (a((b)|((d)))c)로 적을 수도 있으며, 둘은 같은 회로를 나타낸다.

두 회로 C와 D가 주어질 때, 두 출력의 관계를 나타내는 한 글자를 아래 표에 따라 출력한다.

모든 회로는 적어도 하나의 신호를 만들어 낸다고 가정한다. 즉, 출력이 공집합 {}인 회로는 없다. 1이나 (1|1)처럼 통과 소자만으로 이루어진 부분 회로는 여전히 허용되는데, 그 출력은 빈 신호 하나만을 원소로 갖는 집합이라 공집합과는 다르기 때문이다.

첫 줄에 테스트 케이스의 수 T가 주어진다 (T < 30). 이어지는 T개의 줄에는 각각 하나의 테스트 케이스가 주어지며, 한 줄에 두 회로 표기가 하나 이상의 공백으로 구분되어 있다. 각 회로 표기의 길이는 50 미만이다.

각 테스트 케이스마다, 두 회로 C와 D의 관계를 나타내는 한 글자(=, <, >, 0, 1 중 하나)를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다. 출력 줄 수는 테스트 케이스 수와 같다.