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'


-----Input-----

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 $x = \lfloor \frac{j}{4} \rfloor$, $y = \lfloor \frac{j}{2} \rfloor \operatorname{mod} 2$ and $z = j \operatorname{mod} 2$.


-----Output-----

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.


-----Example-----
Input
4
00110011
00000111
11110000
00011111

Output
y
(y|z)&x
!x
x|y&z



-----Note-----

The truth table for the second function:

[Image]

Difficulty: interview

Starter code:

Solutions:
f =['!x&x', '!(x|y|z)', '!x&!y&z', '!x&!y', '!x&!z&y', '!x&!z', '!(!y&!z|x|y&z)', '!(x|y&z)', '!x&y&z', '!(!y&z|!z&y|x)', '!x&z', '!(!z&y|x)', '!x&y', '!(!y&z|x)', '!x&(y|z)', '!x', '!y&!z&x', '!y&!z', '!(!x&!z|x&z|y)', '!(x&z|y)', '!(!x&!y|x&y|z)', '!(x&y|z)', '!(!x&!y|x&y|z)|!x&!y&z', '!((x|y)&z|x&y)', '!x&y&z|!y&!z&x', '!x&y&z|!y&!z', '!x&z|!y&!z&x', '!x&z|!y&!z', '!x&y|!y&!z&x', '!x&y|!y&!z', '!x&(y|z)|!y&!z&x', '!x|!y&!z', '!y&x&z', '!(!x&z|!z&x|y)', '!y&z', '!(!z&x|y)', '!x&!z&y|!y&x&z', '!x&!z|!y&x&z', '!x&!z&y|!y&z', '!x&!z|!y&z', '!x&y&z|!y&x&z', '!(!x&z|!z&x|y)|!x&y&z', '!(x&y)&z', '!(!z&x|y)|!x&z', '!x&y|!y&x&z', '!(!y&z|x)|!y&x&z', '!x&y|!y&z', '!x|!y&z', '!y&x', '!(!x&z|y)', '!y&(x|z)', '!y', '!x&!z&y|!y&x', '!x&!z|!y&x', '!x&!z&y|!y&(x|z)', '!x&!z|!y', '!x&y&z|!y&x', '!(!x&z|y)|!x&y&z', '!x&z|!y&x', '!x&z|!y', '!x&y|!y&x', '!(!x&!y&z|x&y)', '!x&(y|z)|!y&x', '!x|!y', '!z&x&y', '!(!x&y|!y&x|z)', '!x&!y&z|!z&x&y', '!x&!y|!z&x&y', '!z&y', '!(!y&x|z)', '!x&!y&z|!z&y', '!x&!y|!z&y', '!x&y&z|!z&x&y', '!(!x&y|!y&x|z)|!x&y&z', '!x&z|!z&x&y', '!(!z&y|x)|!z&x&y', '!(x&z)&y', '!(!y&x|z)|!x&y', '!x&z|!z&y', '!x|!z&y', '!z&x', '!(!x&y|z)', '!x&!y&z|!z&x', '!x&!y|!z&x', '!z&(x|y)', '!z', '!x&!y&z|!z&(x|y)', '!x&!y|!z', '!x&y&z|!z&x', '!(!x&y|z)|!x&y&z', '!x&z|!z&x', '!(!x&!z&y|x&z)', '!x&y|!z&x', '!x&y|!z', '!x&(y|z)|!z&x', '!x|!z', '!y&x&z|!z&x&y', '!(!x&y|!y&x|z)|!y&x&z', '!y&z|!z&x&y', '!(!z&x|y)|!z&x&y', '!y&x&z|!z&y', '!(!y&x|z)|!y&x&z', '!y&z|!z&y', '!(!y&!z&x|y&z)', '!x&y&z|!y&x&z|!z&x&y', '!(!x&y|!y&x|z)|!x&y&z|!y&x&z', '!(x&y)&z|!z&x&y', '!(!z&x|y)|!x&z|!z&x&y', '!(x&z)&y|!y&x&z', '!(!y&x|z)|!x&y|!y&x&z', '!(x&y)&z|!z&y', '!x|!y&z|!z&y', '!(y&z)&x', '!(!x&y|z)|!y&x', '!y&z|!z&x', '!y|!z&x', '!y&x|!z&y', '!y&x|!z', '!y&(x|z)|!z&y', '!y|!z', '!(y&z)&x|!x&y&z', '!(!x&y|z)|!x&y&z|!y&x', '!(x&y)&z|!z&x', '!x&z|!y|!z&x', '!(x&z)&y|!y&x', '!x&y|!y&x|!z', '!x&y|!y&z|!z&x', '!(x&y&z)', 'x&y&z', '!(x|y|z)|x&y&z', '!x&!y&z|x&y&z', '!x&!y|x&y&z', '!x&!z&y|x&y&z', '!x&!z|x&y&z', '!(!y&!z|x|y&z)|x&y&z', '!(x|y&z)|x&y&z', 'y&z', '!(x|y|z)|y&z', '!x&z|y&z', '!x&!y|y&z', '!x&y|y&z', '!x&!z|y&z', '!x&(y|z)|y&z', '!x|y&z', '!y&!z&x|x&y&z', '!y&!z|x&y&z', '!(!x&!z|x&z|y)|x&y&z', '!(x&z|y)|x&y&z', '!(!x&!y|x&y|z)|x&y&z', '!(x&y|z)|x&y&z', '!(!x&!y|x&y|z)|!x&!y&z|x&y&z', '!((x|y)&z|x&y)|x&y&z', '!y&!z&x|y&z', '!y&!z|y&z', '!x&z|!y&!z&x|y&z', '!(x&z|y)|y&z', '!x&y|!y&!z&x|y&z', '!(x&y|z)|y&z', '!x&(y|z)|!y&!z&x|y&z', '!x|!y&!z|y&z', 'x&z', '!(x|y|z)|x&z', '!y&z|x&z', '!x&!y|x&z', '!x&!z&y|x&z', '!x&!z|x&z', '!x&!z&y|!y&z|x&z', '!(x|y&z)|x&z', '(x|y)&z', '!(x|y|z)|(x|y)&z', 'z', '!x&!y|z', '!x&y|x&z', '!(!y&z|x)|x&z', '!x&y|z', '!x|z', '!y&x|x&z', '!y&!z|x&z', '!y&(x|z)|x&z', '!y|x&z', '!x&!z&y|!y&x|x&z', '!(x&y|z)|x&z', '!x&!z&y|!y&(x|z)|x&z', '!x&!z|!y|x&z', '!y&x|y&z', '!(!x&z|y)|y&z', '!y&x|z', '!y|z', '!x&y|!y&x|x&z', '!x&!z|!y&x|y&z', '!x&y|!y&x|z', '!x|!y|z', 'x&y', '!(x|y|z)|x&y', '!x&!y&z|x&y', '!x&!y|x&y', '!z&y|x&y', '!x&!z|x&y', '!x&!y&z|!z&y|x&y', '!(x|y&z)|x&y', '(x|z)&y', '!(x|y|z)|(x|z)&y', '!x&z|x&y', '!(!z&y|x)|x&y', 'y', '!x&!z|y', '!x&z|y', '!x|y', '!z&x|x&y', '!y&!z|x&y', '!x&!y&z|!z&x|x&y', '!(x&z|y)|x&y', '!z&(x|y)|x&y', '!z|x&y', '!x&!y&z|!z&(x|y)|x&y', '!x&!y|!z|x&y', '!z&x|y&z', '!(!x&y|z)|y&z', '!x&z|!z&x|x&y', '!x&!y|!z&x|y&z', '!z&x|y', '!z|y', '!x&z|!z&x|y', '!x|!z|y', '(y|z)&x', '!(x|y|z)|(y|z)&x', '!y&z|x&y', '!(!z&x|y)|x&y', '!z&y|x&z', '!(!y&x|z)|x&z', '!y&z|!z&y|x&y', '!x&!y|!z&y|x&z', '(x|y)&z|x&y', '!(x|y|z)|(x|y)&z|x&y', 'x&y|z', '!x&!y|x&y|z', 'x&z|y', '!x&!z|x&z|y', 'y|z', '!x|y|z', 'x', '!y&!z|x', '!y&z|x', '!y|x', '!z&y|x', '!z|x', '!y&z|!z&y|x', '!y|!z|x', 'x|y&z', '!y&!z|x|y&z', 'x|z', '!y|x|z', 'x|y', '!z|x|y', 'x|y|z', '!x|x']
n = int(input())
for i in range(n):
    s = input()
    a = 0
    for j in range(8):
        a += int(s[j] == '1') << j

    print(f[a])


val='''!x&x
x&y&z
!z&x&y
x&y
!y&x&z
x&z
!y&x&z|!z&x&y
(y|z)&x
!y&!z&x
!y&!z&x|x&y&z
!z&x
!z&x|x&y
!y&x
!y&x|x&z
!(y&z)&x
x
!x&y&z
y&z
!x&y&z|!z&x&y
(x|z)&y
!x&y&z|!y&x&z
(x|y)&z
!x&y&z|!y&x&z|!z&x&y
(x|y)&z|x&y
!x&y&z|!y&!z&x
!y&!z&x|y&z
!x&y&z|!z&x
!z&x|y&z
!x&y&z|!y&x
!y&x|y&z
!(y&z)&x|!x&y&z
x|y&z
!x&!z&y
!x&!z&y|x&y&z
!z&y
!z&y|x&y
!x&!z&y|!y&x&z
!x&!z&y|x&z
!y&x&z|!z&y
!z&y|x&z
!(!x&!y|x&y|z)
!(!x&!y|x&y|z)|x&y&z
!z&(x|y)
!z&(x|y)|x&y
!x&!z&y|!y&x
!x&!z&y|!y&x|x&z
!y&x|!z&y
!z&y|x
!x&y
!x&y|y&z
!(x&z)&y
y
!x&y|!y&x&z
!x&y|x&z
!(x&z)&y|!y&x&z
x&z|y
!x&y|!y&!z&x
!x&y|!y&!z&x|y&z
!x&y|!z&x
!z&x|y
!x&y|!y&x
!x&y|!y&x|x&z
!(x&z)&y|!y&x
x|y
!x&!y&z
!x&!y&z|x&y&z
!x&!y&z|!z&x&y
!x&!y&z|x&y
!y&z
!y&z|x&z
!y&z|!z&x&y
!y&z|x&y
!(!x&!z|x&z|y)
!(!x&!z|x&z|y)|x&y&z
!x&!y&z|!z&x
!x&!y&z|!z&x|x&y
!y&(x|z)
!y&(x|z)|x&z
!y&z|!z&x
!y&z|x
!x&z
!x&z|y&z
!x&z|!z&x&y
!x&z|x&y
!(x&y)&z
z
!(x&y)&z|!z&x&y
x&y|z
!x&z|!y&!z&x
!x&z|!y&!z&x|y&z
!x&z|!z&x
!x&z|!z&x|x&y
!x&z|!y&x
!y&x|z
!(x&y)&z|!z&x
x|z
!(!y&!z|x|y&z)
!(!y&!z|x|y&z)|x&y&z
!x&!y&z|!z&y
!x&!y&z|!z&y|x&y
!x&!z&y|!y&z
!x&!z&y|!y&z|x&z
!y&z|!z&y
!y&z|!z&y|x&y
!(!x&!y|x&y|z)|!x&!y&z
!(!x&!y|x&y|z)|!x&!y&z|x&y&z
!x&!y&z|!z&(x|y)
!x&!y&z|!z&(x|y)|x&y
!x&!z&y|!y&(x|z)
!x&!z&y|!y&(x|z)|x&z
!y&(x|z)|!z&y
!y&z|!z&y|x
!x&(y|z)
!x&(y|z)|y&z
!x&z|!z&y
!x&z|y
!x&y|!y&z
!x&y|z
!(x&y)&z|!z&y
y|z
!x&(y|z)|!y&!z&x
!x&(y|z)|!y&!z&x|y&z
!x&(y|z)|!z&x
!x&z|!z&x|y
!x&(y|z)|!y&x
!x&y|!y&x|z
!x&y|!y&z|!z&x
x|y|z
!(x|y|z)
!(x|y|z)|x&y&z
!(!x&y|!y&x|z)
!(x|y|z)|x&y
!(!x&z|!z&x|y)
!(x|y|z)|x&z
!(!x&y|!y&x|z)|!y&x&z
!(x|y|z)|(y|z)&x
!y&!z
!y&!z|x&y&z
!(!x&y|z)
!y&!z|x&y
!(!x&z|y)
!y&!z|x&z
!(!x&y|z)|!y&x
!y&!z|x
!(!y&z|!z&y|x)
!(x|y|z)|y&z
!(!x&y|!y&x|z)|!x&y&z
!(x|y|z)|(x|z)&y
!(!x&z|!z&x|y)|!x&y&z
!(x|y|z)|(x|y)&z
!(!x&y|!y&x|z)|!x&y&z|!y&x&z
!(x|y|z)|(x|y)&z|x&y
!x&y&z|!y&!z
!y&!z|y&z
!(!x&y|z)|!x&y&z
!(!x&y|z)|y&z
!(!x&z|y)|!x&y&z
!(!x&z|y)|y&z
!(!x&y|z)|!x&y&z|!y&x
!y&!z|x|y&z
!x&!z
!x&!z|x&y&z
!(!y&x|z)
!x&!z|x&y
!x&!z|!y&x&z
!x&!z|x&z
!(!y&x|z)|!y&x&z
!(!y&x|z)|x&z
!(x&y|z)
!(x&y|z)|x&y&z
!z
!z|x&y
!x&!z|!y&x
!(x&y|z)|x&z
!y&x|!z
!z|x
!(!y&z|x)
!x&!z|y&z
!(!y&x|z)|!x&y
!x&!z|y
!(!y&z|x)|!y&x&z
!(!y&z|x)|x&z
!(!y&x|z)|!x&y|!y&x&z
!x&!z|x&z|y
!x&y|!y&!z
!(x&y|z)|y&z
!x&y|!z
!z|y
!(!x&!y&z|x&y)
!x&!z|!y&x|y&z
!x&y|!y&x|!z
!z|x|y
!x&!y
!x&!y|x&y&z
!x&!y|!z&x&y
!x&!y|x&y
!(!z&x|y)
!x&!y|x&z
!(!z&x|y)|!z&x&y
!(!z&x|y)|x&y
!(x&z|y)
!(x&z|y)|x&y&z
!x&!y|!z&x
!(x&z|y)|x&y
!y
!y|x&z
!y|!z&x
!y|x
!(!z&y|x)
!x&!y|y&z
!(!z&y|x)|!z&x&y
!(!z&y|x)|x&y
!(!z&x|y)|!x&z
!x&!y|z
!(!z&x|y)|!x&z|!z&x&y
!x&!y|x&y|z
!x&z|!y&!z
!(x&z|y)|y&z
!(!x&!z&y|x&z)
!x&!y|!z&x|y&z
!x&z|!y
!y|z
!x&z|!y|!z&x
!y|x|z
!(x|y&z)
!(x|y&z)|x&y&z
!x&!y|!z&y
!(x|y&z)|x&y
!x&!z|!y&z
!(x|y&z)|x&z
!(!y&!z&x|y&z)
!x&!y|!z&y|x&z
!((x|y)&z|x&y)
!((x|y)&z|x&y)|x&y&z
!x&!y|!z
!x&!y|!z|x&y
!x&!z|!y
!x&!z|!y|x&z
!y|!z
!y|!z|x
!x
!x|y&z
!x|!z&y
!x|y
!x|!y&z
!x|z
!x|!y&z|!z&y
!x|y|z
!x|!y&!z
!x|!y&!z|y&z
!x|!z
!x|!z|y
!x|!y
!x|!y|z
!(x&y&z)
!x|x'''.split()

for _ in range(int(input())):
	n=0
	for b in input():
		n<<=1
		if b=='1':
			n|=1
	print(val[n])



sol = {'01010101': 'z', '00110011': 'y', '00001111': 'x', '10101010': '!z', '11001100': '!y', '11110000': '!x', '01110111': 'y|z', '01011111': 'x|z', '00010001': 'y&z', '00000101': 'x&z', '00111111': 'x|y', '00000011': 'x&y', '11111111': '!x|x', '11011101': '!y|z', '11110101': '!x|z', '00000000': '!x&x', '01000100': '!y&z', '01010000': '!x&z', '10111011': '!z|y', '11110011': '!x|y', '00100010': '!z&y', '00110000': '!x&y', '10101111': '!z|x', '11001111': '!y|x', '00001010': '!z&x', '00001100': '!y&x', '01111111': 'x|y|z', '01010111': 'x&y|z', '00011111': 'x|y&z', '00000001': 'x&y&z', '00110111': 'x&z|y', '11110111': '!x|y|z', '01110101': '!x&y|z', '11011111': '!y|x|z', '01011101': '!y&x|z', '11110001': '!x|y&z', '00010000': '!x&y&z', '11001101': '!y|x&z', '00000100': '!y&x&z', '01110011': '!x&z|y', '10111111': '!z|x|y', '00111011': '!z&x|y', '10101011': '!z|x&y', '00000010': '!z&x&y', '01001111': '!y&z|x', '00101111': '!z&y|x', '10001000': '!y&!z', '10100000': '!x&!z', '11101110': '!y|!z', '11111010': '!x|!z', '11000000': '!x&!y', '11111100': '!x|!y', '00010101': '(x|y)&z', '00010011': '(x|z)&y', '00000111': '(y|z)&x', '11010101': '!x&!y|z', '11111101': '!x|!y|z', '01010001': '!x&z|y&z', '00110001': '!x&y|y&z', '00011011': '!z&x|y&z', '00011101': '!y&x|y&z', '01000101': '!y&z|x&z', '00100111': '!z&y|x&z', '00110101': '!x&y|x&z', '00001101': '!y&x|x&z', '01000000': '!x&!y&z', '01010100': '!(x&y)&z', '10110011': '!x&!z|y', '11111011': '!x|!z|y', '01000111': '!y&z|x&y', '01010011': '!x&z|x&y', '00100011': '!z&y|x&y', '00001011': '!z&x|x&y', '00100000': '!x&!z&y', '00110010': '!(x&z)&y', '10001111': '!y&!z|x', '11101111': '!y|!z|x', '00001000': '!y&!z&x', '00001110': '!(y&z)&x', '10000000': '!(x|y|z)', '01110000': '!x&(y|z)', '10101000': '!(x&y|z)', '01001100': '!y&(x|z)', '11100000': '!(x|y&z)', '11111110': '!(x&y&z)', '11001000': '!(x&z|y)', '00101010': '!z&(x|y)', '10100010': '!(!y&x|z)', '10111010': '!x&y|!z', '10001010': '!(!x&y|z)', '10101110': '!y&x|!z', '10110001': '!x&!z|y&z', '10001101': '!y&!z|x&z', '11101010': '!x&!y|!z', '00011001': '!y&!z&x|y&z', '00100101': '!x&!z&y|x&z', '11000100': '!(!z&x|y)', '11011100': '!x&z|!y', '10001100': '!(!x&z|y)', '11001110': '!y|!z&x', '11010001': '!x&!y|y&z', '10001011': '!y&!z|x&y', '11101100': '!x&!z|!y', '01000011': '!x&!y&z|x&y', '11010000': '!(!z&y|x)', '11110100': '!x|!y&z', '10110000': '!(!y&z|x)', '11110010': '!x|!z&y', '11000101': '!x&!y|x&z', '10100011': '!x&!z|x&y', '11111000': '!x|!y&!z', '00010111': '(x|y)&z|x&y', '01110001': '!x&(y|z)|y&z', '01100110': '!y&z|!z&y', '01110010': '!x&z|!z&y', '01110100': '!x&y|!y&z', '01101111': '!y&z|!z&y|x', '01100111': '!y&z|!z&y|x&y', '00000110': '!y&x&z|!z&x&y', '01100000': '!(!y&!z|x|y&z)', '01110110': '!(x&y)&z|!z&y', '01001101': '!y&(x|z)|x&z', '01001110': '!y&z|!z&x', '01011010': '!x&z|!z&x', '01011100': '!x&z|!y&x', '01111011': '!x&z|!z&x|y', '01011011': '!x&z|!z&x|x&y', '00010010': '!x&y&z|!z&x&y', '01011110': '!(x&y)&z|!z&x', '01001000': '!(!x&!z|x&z|y)', '10011001': '!y&!z|y&z', '10011111': '!y&!z|x|y&z', '10010001': '!(x|y|z)|y&z', '10111001': '!(x&y|z)|y&z', '11011001': '!(x&z|y)|y&z', '10100101': '!x&!z|x&z', '10110111': '!x&!z|x&z|y', '10000101': '!(x|y|z)|x&z', '10101101': '!(x&y|z)|x&z', '11100101': '!(x|y&z)|x&z', '00101011': '!z&(x|y)|x&y', '00101110': '!y&x|!z&y', '00111010': '!x&y|!z&x', '00111100': '!x&y|!y&x', '01111101': '!x&y|!y&x|z', '00111101': '!x&y|!y&x|x&z', '00010100': '!x&y&z|!y&x&z', '00101000': '!(!x&!y|x&y|z)', '00111110': '!(x&z)&y|!y&x', '11000011': '!x&!y|x&y', '11010111': '!x&!y|x&y|z', '10000011': '!(x|y|z)|x&y', '11100011': '!(x|y&z)|x&y', '11001011': '!(x&z|y)|x&y', '10011101': '!(!x&z|y)|y&z', '10001001': '!y&!z|x&y&z', '11011000': '!x&z|!y&!z', '00001001': '!y&!z&x|x&y&z', '10110101': '!(!y&z|x)|x&z', '10100001': '!x&!z|x&y&z', '11100100': '!x&!z|!y&z', '00100001': '!x&!z&y|x&y&z', '01000110': '!y&z|!z&x&y', '01100100': '!x&!z&y|!y&z', '01101110': '!y&(x|z)|!z&y', '01010010': '!x&z|!z&x&y', '01011000': '!x&z|!y&!z&x', '01111010': '!x&(y|z)|!z&x', '10011011': '!(!x&y|z)|y&z', '10111000': '!x&y|!y&!z', '11010011': '!(!z&y|x)|x&y', '11000001': '!x&!y|x&y&z', '11100010': '!x&!y|!z&y', '01000001': '!x&!y&z|x&y&z', '00100110': '!y&x&z|!z&y', '01100010': '!x&!y&z|!z&y', '00110100': '!x&y|!y&x&z', '00111000': '!x&y|!y&!z&x', '01111100': '!x&(y|z)|!y&x', '10100111': '!(!y&x|z)|x&z', '10101100': '!x&!z|!y&x', '11000111': '!(!z&x|y)|x&y', '11001010': '!x&!y|!z&x', '00011010': '!x&y&z|!z&x', '01001010': '!x&!y&z|!z&x', '00011100': '!x&y&z|!y&x', '00101100': '!x&!z&y|!y&x', '01111110': '!x&y|!y&z|!z&x', '01010110': '!(x&y)&z|!z&x&y', '00011110': '!(y&z)&x|!x&y&z', '10000001': '!(x|y|z)|x&y&z', '10101001': '!(x&y|z)|x&y&z', '11100001': '!(x|y&z)|x&y&z', '11001001': '!(x&z|y)|x&y&z', '00110110': '!(x&z)&y|!y&x&z', '11100110': '!(!y&!z&x|y&z)', '10000111': '!(x|y|z)|(y|z)&x', '11100111': '!x&!y|!z&y|x&z', '11110110': '!x|!y&z|!z&y', '01100101': '!x&!z&y|!y&z|x&z', '11011010': '!(!x&!z&y|x&z)', '10010011': '!(x|y|z)|(x|z)&y', '11011011': '!x&!y|!z&x|y&z', '11011110': '!x&z|!y|!z&x', '01011001': '!x&z|!y&!z&x|y&z', '11111001': '!x|!y&!z|y&z', '10011000': '!x&y&z|!y&!z', '00011000': '!x&y&z|!y&!z&x', '10010000': '!(!y&z|!z&y|x)', '11101101': '!x&!z|!y|x&z', '10100100': '!x&!z|!y&x&z', '00100100': '!x&!z&y|!y&x&z', '10000100': '!(!x&z|!z&x|y)', '01100011': '!x&!y&z|!z&y|x&y', '10111100': '!(!x&!y&z|x&y)', '10010101': '!(x|y|z)|(x|y)&z', '10111101': '!x&!z|!y&x|y&z', '10111110': '!x&y|!y&x|!z', '00111001': '!x&y|!y&!z&x|y&z', '11101011': '!x&!y|!z|x&y', '11000010': '!x&!y|!z&x&y', '01000010': '!x&!y&z|!z&x&y', '10000010': '!(!x&y|!y&x|z)', '01001011': '!x&!y&z|!z&x|x&y', '00101101': '!x&!z&y|!y&x|x&z', '10001110': '!(!x&y|z)|!y&x', '11101000': '!((x|y)&z|x&y)', '10110010': '!(!y&x|z)|!x&y', '11010100': '!(!z&x|y)|!x&z', '01101010': '!x&!y&z|!z&(x|y)', '01101100': '!x&!z&y|!y&(x|z)', '01111000': '!x&(y|z)|!y&!z&x', '00010110': '!x&y&z|!y&x&z|!z&x&y', '01100001': '!(!y&!z|x|y&z)|x&y&z', '01001001': '!(!x&!z|x&z|y)|x&y&z', '10010111': '!(x|y|z)|(x|y)&z|x&y', '01111001': '!x&(y|z)|!y&!z&x|y&z', '01101101': '!x&!z&y|!y&(x|z)|x&z', '00101001': '!(!x&!y|x&y|z)|x&y&z', '01101011': '!x&!y&z|!z&(x|y)|x&y', '10011100': '!(!x&z|y)|!x&y&z', '10110100': '!(!y&z|x)|!y&x&z', '11000110': '!(!z&x|y)|!z&x&y', '11010010': '!(!z&y|x)|!z&x&y', '10011010': '!(!x&y|z)|!x&y&z', '10100110': '!(!y&x|z)|!y&x&z', '01101000': '!(!x&!y|x&y|z)|!x&!y&z', '11101001': '!((x|y)&z|x&y)|x&y&z', '11010110': '!(!z&x|y)|!x&z|!z&x&y', '10110110': '!(!y&x|z)|!x&y|!y&x&z', '10000110': '!(!x&y|!y&x|z)|!y&x&z', '10011110': '!(!x&y|z)|!x&y&z|!y&x', '10010010': '!(!x&y|!y&x|z)|!x&y&z', '10010100': '!(!x&z|!z&x|y)|!x&y&z', '01101001': '!(!x&!y|x&y|z)|!x&!y&z|x&y&z', '10010110': '!(!x&y|!y&x|z)|!x&y&z|!y&x&z'}
n = int(input())
for i in range(n):
	print(sol[input()])


answers = [
'!x&x',
'x&y&z',
'!z&x&y',
'x&y',
'!y&x&z',
'x&z',
'!y&x&z|!z&x&y',
'(y|z)&x',
'!y&!z&x',
'!y&!z&x|x&y&z',
'!z&x',
'!z&x|x&y',
'!y&x',
'!y&x|x&z',
'!(y&z)&x',
'x',
'!x&y&z',
'y&z',
'!x&y&z|!z&x&y',
'(x|z)&y',
'!x&y&z|!y&x&z',
'(x|y)&z',
'!x&y&z|!y&x&z|!z&x&y',
'(x|y)&z|x&y',
'!x&y&z|!y&!z&x',
'!y&!z&x|y&z',
'!x&y&z|!z&x',
'!z&x|y&z',
'!x&y&z|!y&x',
'!y&x|y&z',
'!(y&z)&x|!x&y&z',
'x|y&z',
'!x&!z&y',
'!x&!z&y|x&y&z',
'!z&y',
'!z&y|x&y',
'!x&!z&y|!y&x&z',
'!x&!z&y|x&z',
'!y&x&z|!z&y',
'!z&y|x&z',
'!(!x&!y|x&y|z)',
'!(!x&!y|x&y|z)|x&y&z',
'!z&(x|y)',
'!z&(x|y)|x&y',
'!x&!z&y|!y&x',
'!x&!z&y|!y&x|x&z',
'!y&x|!z&y',
'!z&y|x',
'!x&y',
'!x&y|y&z',
'!(x&z)&y',
'y',
'!x&y|!y&x&z',
'!x&y|x&z',
'!(x&z)&y|!y&x&z',
'x&z|y',
'!x&y|!y&!z&x',
'!x&y|!y&!z&x|y&z',
'!x&y|!z&x',
'!z&x|y',
'!x&y|!y&x',
'!x&y|!y&x|x&z',
'!(x&z)&y|!y&x',
'x|y',
'!x&!y&z',
'!x&!y&z|x&y&z',
'!x&!y&z|!z&x&y',
'!x&!y&z|x&y',
'!y&z',
'!y&z|x&z',
'!y&z|!z&x&y',
'!y&z|x&y',
'!(!x&!z|x&z|y)',
'!(!x&!z|x&z|y)|x&y&z',
'!x&!y&z|!z&x',
'!x&!y&z|!z&x|x&y',
'!y&(x|z)',
'!y&(x|z)|x&z',
'!y&z|!z&x',
'!y&z|x',
'!x&z',
'!x&z|y&z',
'!x&z|!z&x&y',
'!x&z|x&y',
'!(x&y)&z',
'z',
'!(x&y)&z|!z&x&y',
'x&y|z',
'!x&z|!y&!z&x',
'!x&z|!y&!z&x|y&z',
'!x&z|!z&x',
'!x&z|!z&x|x&y',
'!x&z|!y&x',
'!y&x|z',
'!(x&y)&z|!z&x',
'x|z',
'!(!y&!z|x|y&z)',
'!(!y&!z|x|y&z)|x&y&z',
'!x&!y&z|!z&y',
'!x&!y&z|!z&y|x&y',
'!x&!z&y|!y&z',
'!x&!z&y|!y&z|x&z',
'!y&z|!z&y',
'!y&z|!z&y|x&y',
'!(!x&!y|x&y|z)|!x&!y&z',
'!(!x&!y|x&y|z)|!x&!y&z|x&y&z',
'!x&!y&z|!z&(x|y)',
'!x&!y&z|!z&(x|y)|x&y',
'!x&!z&y|!y&(x|z)',
'!x&!z&y|!y&(x|z)|x&z',
'!y&(x|z)|!z&y',
'!y&z|!z&y|x',
'!x&(y|z)',
'!x&(y|z)|y&z',
'!x&z|!z&y',
'!x&z|y',
'!x&y|!y&z',
'!x&y|z',
'!(x&y)&z|!z&y',
'y|z',
'!x&(y|z)|!y&!z&x',
'!x&(y|z)|!y&!z&x|y&z',
'!x&(y|z)|!z&x',
'!x&z|!z&x|y',
'!x&(y|z)|!y&x',
'!x&y|!y&x|z',
'!x&y|!y&z|!z&x',
'x|y|z',
'!(x|y|z)',
'!(x|y|z)|x&y&z',
'!(!x&y|!y&x|z)',
'!(x|y|z)|x&y',
'!(!x&z|!z&x|y)',
'!(x|y|z)|x&z',
'!(!x&y|!y&x|z)|!y&x&z',
'!(x|y|z)|(y|z)&x',
'!y&!z',
'!y&!z|x&y&z',
'!(!x&y|z)',
'!y&!z|x&y',
'!(!x&z|y)',
'!y&!z|x&z',
'!(!x&y|z)|!y&x',
'!y&!z|x',
'!(!y&z|!z&y|x)',
'!(x|y|z)|y&z',
'!(!x&y|!y&x|z)|!x&y&z',
'!(x|y|z)|(x|z)&y',
'!(!x&z|!z&x|y)|!x&y&z',
'!(x|y|z)|(x|y)&z',
'!(!x&y|!y&x|z)|!x&y&z|!y&x&z',
'!(x|y|z)|(x|y)&z|x&y',
'!x&y&z|!y&!z',
'!y&!z|y&z',
'!(!x&y|z)|!x&y&z',
'!(!x&y|z)|y&z',
'!(!x&z|y)|!x&y&z',
'!(!x&z|y)|y&z',
'!(!x&y|z)|!x&y&z|!y&x',
'!y&!z|x|y&z',
'!x&!z',
'!x&!z|x&y&z',
'!(!y&x|z)',
'!x&!z|x&y',
'!x&!z|!y&x&z',
'!x&!z|x&z',
'!(!y&x|z)|!y&x&z',
'!(!y&x|z)|x&z',
'!(x&y|z)',
'!(x&y|z)|x&y&z',
'!z',
'!z|x&y',
'!x&!z|!y&x',
'!(x&y|z)|x&z',
'!y&x|!z',
'!z|x',
'!(!y&z|x)',
'!x&!z|y&z',
'!(!y&x|z)|!x&y',
'!x&!z|y',
'!(!y&z|x)|!y&x&z',
'!(!y&z|x)|x&z',
'!(!y&x|z)|!x&y|!y&x&z',
'!x&!z|x&z|y',
'!x&y|!y&!z',
'!(x&y|z)|y&z',
'!x&y|!z',
'!z|y',
'!(!x&!y&z|x&y)',
'!x&!z|!y&x|y&z',
'!x&y|!y&x|!z',
'!z|x|y',
'!x&!y',
'!x&!y|x&y&z',
'!x&!y|!z&x&y',
'!x&!y|x&y',
'!(!z&x|y)',
'!x&!y|x&z',
'!(!z&x|y)|!z&x&y',
'!(!z&x|y)|x&y',
'!(x&z|y)',
'!(x&z|y)|x&y&z',
'!x&!y|!z&x',
'!(x&z|y)|x&y',
'!y',
'!y|x&z',
'!y|!z&x',
'!y|x',
'!(!z&y|x)',
'!x&!y|y&z',
'!(!z&y|x)|!z&x&y',
'!(!z&y|x)|x&y',
'!(!z&x|y)|!x&z',
'!x&!y|z',
'!(!z&x|y)|!x&z|!z&x&y',
'!x&!y|x&y|z',
'!x&z|!y&!z',
'!(x&z|y)|y&z',
'!(!x&!z&y|x&z)',
'!x&!y|!z&x|y&z',
'!x&z|!y',
'!y|z',
'!x&z|!y|!z&x',
'!y|x|z',
'!(x|y&z)',
'!(x|y&z)|x&y&z',
'!x&!y|!z&y',
'!(x|y&z)|x&y',
'!x&!z|!y&z',
'!(x|y&z)|x&z',
'!(!y&!z&x|y&z)',
'!x&!y|!z&y|x&z',
'!((x|y)&z|x&y)',
'!((x|y)&z|x&y)|x&y&z',
'!x&!y|!z',
'!x&!y|!z|x&y',
'!x&!z|!y',
'!x&!z|!y|x&z',
'!y|!z',
'!y|!z|x',
'!x',
'!x|y&z',
'!x|!z&y',
'!x|y',
'!x|!y&z',
'!x|z',
'!x|!y&z|!z&y',
'!x|y|z',
'!x|!y&!z',
'!x|!y&!z|y&z',
'!x|!z',
'!x|!z|y',
'!x|!y',
'!x|!y|z',
'!(x&y&z)',
'!x|x']

N = int(input())
for i in range(N):
    q = int(input(), 2)
    print(answers[q])


table = "!x&x x&y&z !z&x&y x&y !y&x&z x&z !y&x&z|!z&x&y (y|z)&x !y&!z&x !y&!z&x|x&y&z !z&x !z&x|x&y !y&x !y&x|x&z !(y&z)&x x !x&y&z y&z !x&y&z|!z&x&y (x|z)&y !x&y&z|!y&x&z (x|y)&z !x&y&z|!y&x&z|!z&x&y (x|y)&z|x&y !x&y&z|!y&!z&x !y&!z&x|y&z !x&y&z|!z&x !z&x|y&z !x&y&z|!y&x !y&x|y&z !(y&z)&x|!x&y&z x|y&z !x&!z&y !x&!z&y|x&y&z !z&y !z&y|x&y !x&!z&y|!y&x&z !x&!z&y|x&z !y&x&z|!z&y !z&y|x&z !(!x&!y|x&y|z) !(!x&!y|x&y|z)|x&y&z !z&(x|y) !z&(x|y)|x&y !x&!z&y|!y&x !x&!z&y|!y&x|x&z !y&x|!z&y !z&y|x !x&y !x&y|y&z !(x&z)&y y !x&y|!y&x&z !x&y|x&z !(x&z)&y|!y&x&z x&z|y !x&y|!y&!z&x !x&y|!y&!z&x|y&z !x&y|!z&x !z&x|y !x&y|!y&x !x&y|!y&x|x&z !(x&z)&y|!y&x x|y !x&!y&z !x&!y&z|x&y&z !x&!y&z|!z&x&y !x&!y&z|x&y !y&z !y&z|x&z !y&z|!z&x&y !y&z|x&y !(!x&!z|x&z|y) !(!x&!z|x&z|y)|x&y&z !x&!y&z|!z&x !x&!y&z|!z&x|x&y !y&(x|z) !y&(x|z)|x&z !y&z|!z&x !y&z|x !x&z !x&z|y&z !x&z|!z&x&y !x&z|x&y !(x&y)&z z !(x&y)&z|!z&x&y x&y|z !x&z|!y&!z&x !x&z|!y&!z&x|y&z !x&z|!z&x !x&z|!z&x|x&y !x&z|!y&x !y&x|z !(x&y)&z|!z&x x|z !(!y&!z|x|y&z) !(!y&!z|x|y&z)|x&y&z !x&!y&z|!z&y !x&!y&z|!z&y|x&y !x&!z&y|!y&z !x&!z&y|!y&z|x&z !y&z|!z&y !y&z|!z&y|x&y !(!x&!y|x&y|z)|!x&!y&z !(!x&!y|x&y|z)|!x&!y&z|x&y&z !x&!y&z|!z&(x|y) !x&!y&z|!z&(x|y)|x&y !x&!z&y|!y&(x|z) !x&!z&y|!y&(x|z)|x&z !y&(x|z)|!z&y !y&z|!z&y|x !x&(y|z) !x&(y|z)|y&z !x&z|!z&y !x&z|y !x&y|!y&z !x&y|z !(x&y)&z|!z&y y|z !x&(y|z)|!y&!z&x !x&(y|z)|!y&!z&x|y&z !x&(y|z)|!z&x !x&z|!z&x|y !x&(y|z)|!y&x !x&y|!y&x|z !x&y|!y&z|!z&x x|y|z !(x|y|z) !(x|y|z)|x&y&z !(!x&y|!y&x|z) !(x|y|z)|x&y !(!x&z|!z&x|y) !(x|y|z)|x&z !(!x&y|!y&x|z)|!y&x&z !(x|y|z)|(y|z)&x !y&!z !y&!z|x&y&z !(!x&y|z) !y&!z|x&y !(!x&z|y) !y&!z|x&z !(!x&y|z)|!y&x !y&!z|x !(!y&z|!z&y|x) !(x|y|z)|y&z !(!x&y|!y&x|z)|!x&y&z !(x|y|z)|(x|z)&y !(!x&z|!z&x|y)|!x&y&z !(x|y|z)|(x|y)&z !(!x&y|!y&x|z)|!x&y&z|!y&x&z !(x|y|z)|(x|y)&z|x&y !x&y&z|!y&!z !y&!z|y&z !(!x&y|z)|!x&y&z !(!x&y|z)|y&z !(!x&z|y)|!x&y&z !(!x&z|y)|y&z !(!x&y|z)|!x&y&z|!y&x !y&!z|x|y&z !x&!z !x&!z|x&y&z !(!y&x|z) !x&!z|x&y !x&!z|!y&x&z !x&!z|x&z !(!y&x|z)|!y&x&z !(!y&x|z)|x&z !(x&y|z) !(x&y|z)|x&y&z !z !z|x&y !x&!z|!y&x !(x&y|z)|x&z !y&x|!z !z|x !(!y&z|x) !x&!z|y&z !(!y&x|z)|!x&y !x&!z|y !(!y&z|x)|!y&x&z !(!y&z|x)|x&z !(!y&x|z)|!x&y|!y&x&z !x&!z|x&z|y !x&y|!y&!z !(x&y|z)|y&z !x&y|!z !z|y !(!x&!y&z|x&y) !x&!z|!y&x|y&z !x&y|!y&x|!z !z|x|y !x&!y !x&!y|x&y&z !x&!y|!z&x&y !x&!y|x&y !(!z&x|y) !x&!y|x&z !(!z&x|y)|!z&x&y !(!z&x|y)|x&y !(x&z|y) !(x&z|y)|x&y&z !x&!y|!z&x !(x&z|y)|x&y !y !y|x&z !y|!z&x !y|x !(!z&y|x) !x&!y|y&z !(!z&y|x)|!z&x&y !(!z&y|x)|x&y !(!z&x|y)|!x&z !x&!y|z !(!z&x|y)|!x&z|!z&x&y !x&!y|x&y|z !x&z|!y&!z !(x&z|y)|y&z !(!x&!z&y|x&z) !x&!y|!z&x|y&z !x&z|!y !y|z !x&z|!y|!z&x !y|x|z !(x|y&z) !(x|y&z)|x&y&z !x&!y|!z&y !(x|y&z)|x&y !x&!z|!y&z !(x|y&z)|x&z !(!y&!z&x|y&z) !x&!y|!z&y|x&z !((x|y)&z|x&y) !((x|y)&z|x&y)|x&y&z !x&!y|!z !x&!y|!z|x&y !x&!z|!y !x&!z|!y|x&z !y|!z !y|!z|x !x !x|y&z !x|!z&y !x|y !x|!y&z !x|z !x|!y&z|!z&y !x|y|z !x|!y&!z !x|!y&!z|y&z !x|!z !x|!z|y !x|!y !x|!y|z !(x&y&z) !x|x".split()
n = int(input())
for i in range(n):
	print(table[int(input(), 2)])
return


E = set()
T = set()
F = set('xyz')
prv = 0
x = int('00001111', 2)
y = int('00110011', 2)
z = int('01010101', 2)
fam = 2 ** 8
tmpl = '#' * 99
ans = [tmpl] * fam

def cmpr(E):
    nonlocal ans
    ans = [tmpl] * fam
    for e in E:
        res = eval(e.replace('!', '~')) & (fam - 1)
        if len(ans[res]) > len(e) or len(ans[res]) == len(e) and ans[res] > e:
            ans[res] = e
    return set(ans) - {tmpl}

def cmpr3(E, T, F):
    return cmpr(E), cmpr(T), cmpr(F)

while prv != (E, T, F):
    prv = E.copy(), T.copy(), F.copy()
    for f in prv[2]:
        F.add('!' + f)
        T.add(f)
        for t in prv[1]:
            T.add(t + '&' + f)
    for t in prv[1]:
        E.add(t)
    for e in prv[0]:
        if e not in F:
            F.add('(' + e + ')')
        for t in prv[1]:
            E.add(e + '|' + t)
    E, T, F = cmpr3(E, T, F)

cmpr(E)

for f in ans:
    print(f)
    
print(ans.count(tmpl), fam - ans.count(tmpl))

x = int('00001111', 2)
y = int('00110011', 2)
z = int('01010101', 2)
E = set()
T = set()
F = {('x', x), ('y', y), ('z', z)}
prv = (set(), set(), set())
fam = 2 ** 8
tmpl = '#' * 99
ans = [tmpl] * fam
def cmpr(E):
    nonlocal ans
    ans = [tmpl] * fam
    for e in E:
        if len(ans[e[1]]) > len(e[0]) or len(ans[e[1]]) == len(e[0]) and ans[e[1]] > e[0]:
            ans[e[1]] = e[0]
    return set((j, i) for i, j in enumerate(ans) if j != tmpl)
while prv != (E, T, F):
    prv = E.copy(), T.copy(), F.copy()
    for f in prv[2]:
        F.add(('!' + f[0], ~f[1] & (fam - 1)))
        T.add(f)
        for t in prv[1]:
            T.add((t[0] + '&' + f[0], t[1] & f[1]))
    for t in prv[1]:
        E.add(t)
    for e in prv[0]:
        if e not in F:
            F.add(('(' + e[0] + ')', e[1]))
        for t in prv[1]:
            E.add((e[0] + '|' + t[0], e[1] | t[1]))
    E, T, F = cmpr(E), cmpr(T), cmpr(F)
cmpr(E)
n = int(input())
for i in range(n):
	print(ans[int(input(), 2)])

from heapq import *

MSIZE = 1 << 8
def GetVal(s):
    ans = 0
    for i in range(8):
        if s[i] == '1':
            ans = ans + (1 << i)
    return ans

def GetNot(s):
    return MSIZE - 1 - s;

xVal = GetVal('00001111')
yVal = GetVal('00110011')
zVal = GetVal('01010101')

# 0 - |
# 1 - &
# 2 - !
# 3 - ()

def Dijkstra():
    depth = [['Z' * 585 for i in range(4)] for i in range(MSIZE)]
    depth[xVal][3] = 'x'
    depth[yVal][3] = 'y'
    depth[zVal][3] = 'z'

    pq = []
    def push(kek):
        heappush(pq, kek)
    def pop():
        return heappop(pq)
    push([1, xVal, 3])
    push([1, yVal, 3])
    push([1, zVal, 3])
    while len(pq) > 0:
        l, i, j = pop();
        if len(depth[i][j]) < l: continue
        for x in range(MSIZE):
            for y in range(4):
                nxt1 = depth[i][j] + '|' + depth[x][y]
                nxt2 = depth[x][y] + '|' + depth[i][j]
                nxt = min(nxt1, nxt2)
                val = (i | x)
                if len(depth[val][0]) == len(nxt) and depth[val][0] > nxt:
                    depth[val][0] = nxt
                    push([len(nxt), val, 0])
                elif len(depth[val][0]) > len(nxt):
                    depth[val][0] = nxt
                    push([len(nxt), val, 0])
        if j > 0:
            for x in range(MSIZE):
                for y in range(1, 4):
                    nxt1 = depth[i][j] + '&' + depth[x][y]
                    nxt2 = depth[x][y] + '&' + depth[i][j]
                    nxt = min(nxt1, nxt2)
                    val = (i & x)
                    if len(depth[val][1]) == len(nxt) and depth[val][1] > nxt:
                        depth[val][1] = nxt
                        push([len(nxt), val, 1])
                    elif len(depth[val][1]) > len(nxt):
                        depth[val][1] = nxt
                        push([len(nxt), val, 1])
        if j > 2:
            val = GetNot(i)
            nxt = '!' + depth[i][j]
            if len(depth[val][2]) == len(nxt) and depth[val][2] > nxt:
                depth[val][2] = nxt
                push([len(nxt), val, 2])
            elif len(depth[val][2]) > len(nxt):
                depth[val][2] = nxt
                push([len(nxt), val, 2])
        nxt = '(' + depth[i][j] + ')'
        val = i
        if len(depth[val][3]) == len(nxt) and depth[val][3] > nxt:
            depth[val][3] = nxt
            push([len(nxt), val, 3])
        elif len(depth[val][3]) > len(nxt):
            depth[val][3] = nxt
            push([len(nxt), val, 3])
    answer = []
    for i in range(MSIZE):
        ans = 'Z' * 585
        for j in range(4):
            if len(ans) > len(depth[i][j]):
                ans = depth[i][j]
            elif len(ans) == len(depth[i][j]) and ans > depth[i][j]:
                ans = depth[i][j]
        answer.append(ans)
    return answer
kek = Dijkstra()

q = int(input())
for i in range(q):
    print(kek[GetVal(input())])