CF913E.Logical Expression

You are given a boolean function of three variables which is defined by its truth table. You need to find an expression of minimum length that equals to this function. The expression may consist of:

• Operation AND ('&', ASCII code 38)
• Operation OR ('|', ASCII code 124)
• Operation NOT ('!', ASCII code 33)
• Variables x, y and z (ASCII codes 120-122)
• Parentheses ('(', ASCII code 40, and ')', ASCII code 41)

If more than one expression of minimum length exists, you should find the lexicographically smallest one.

Operations have standard priority. NOT has the highest priority, then AND goes, and OR has the lowest priority. The expression should satisfy the following grammar:

E ::= E '|' T | T

T ::= T '&' F | F

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

你将得到一个由真值表定义的三变量布尔函数。你需要找出一个长度最短且与该函数等价的表达式。该表达式可包含以下成分：

• 逻辑与运算符（&，ASCII 码为 38）
• 逻辑或运算符（|，ASCII 码为 124）
• 逻辑非运算符（!，ASCII 码为 33）
• 变量 x、y 和 z（ASCII 码分别为 120–122）
• 圆括号 ( 和 )（ASCII 码分别为 40 和 41）

若存在多个长度最短的表达式，则应选择字典序最小的一个。

各运算符具有标准优先级：逻辑非（!）优先级最高，其次为逻辑与（&），逻辑或（|）优先级最低。表达式须满足如下文法：

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

The first line contains one integer n — the number of functions in the input (1 ≤ n ≤ 10 000).

The following n lines contain descriptions of functions, the i-th of them contains a string of length 8 that consists of digits 0 and 1 — the truth table of the i-th function. The digit on position j (0 ≤ j < 8) equals to the value of the function in case of , and .

第一行包含一个整数 $n$ —— 输入中函数的个数（$1 \leq n \leq 10\,000$）。

接下来的 $n$ 行描述了这些函数，其中第 $i$ 行包含一个长度为 8 的字符串，该字符串仅由数字 0 和 1 组成 —— 即第 $i$ 个函数的真值表。位置 $j$（$0 \leq j < 8$）上的数字等于当 、 和 时该函数的取值。

You should output n lines, the i-th line should contain the expression of minimum length which equals to the i-th function. If there is more than one such expression, output the lexicographically smallest of them. Expressions should satisfy the given grammar and shouldn't contain white spaces.

你需要输出 n 行，其中第 i 行应包含一个长度最小且值等于第 i 个函数的表达式。若存在多个满足条件的表达式，则输出字典序最小的一个。所有表达式必须满足给定的文法，且不得包含空白字符。

The truth table for the second function:

第二个函数的真值表：