Logical Expression

세 변수의 진리표로 정의된 불 함수가 주어진다. 이 함수와 같은 최소 길이의 식을 찾아야 한다. 식은 다음으로 구성될 수 있다.

• Operation AND ('&', ASCII 코드 38)
• Operation OR ('|', ASCII 코드 124)
• Operation NOT ('!', ASCII 코드 33)
• 변수 x, y, z (ASCII 코드 120-122)
• 괄호 ('(', ASCII 코드 40, 그리고 ')', ASCII 코드 41)

최소 길이의 식이 둘 이상 존재한다면, 그중 사전순으로 가장 작은 것을 찾아야 한다.

연산에는 표준 우선순위가 적용된다. NOT의 우선순위가 가장 높고, 그다음은 AND이며, OR의 우선순위가 가장 낮다. 식은 다음 문법을 만족해야 한다.

E ::= E '|' T | T

T ::= T '&' F | F

F ::= '!' F | '(' E ')' | 'x' | 'y' | 'z'

첫째 줄에 입력에 포함된 함수의 수를 나타내는 하나의 정수 n가 주어진다 (1 ≤ n ≤ 10 000).

이어지는 n개의 줄에는 함수에 대한 설명이 주어지며, 그중 i-th 줄에는 i-th 함수의 진리표를 나타내는, 숫자 0과 1로 이루어진 길이 8의 문자열이 주어진다. j (0 ≤ j < 8) 위치의 숫자는 , , 인 경우의 함수 값과 같다.

n개의 줄을 출력해야 한다. i-th 줄에는 i-th 함수와 같은 최소 길이의 식을 출력한다. 그러한 식이 둘 이상이라면, 그중 사전순으로 가장 작은 것을 출력한다. 식은 주어진 문법을 만족해야 하며 공백을 포함해서는 안 된다.

두 번째 함수의 진리표는 다음과 같다.