Logical Expression (Codeforces 913E)
Tags: DP, shortest paths

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 | TT ::= T '&' F | FF ::= '!' 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 ,  and .

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.

Note: The truth table for the second function:

Sample Inputs:
4
00110011
00000111
11110000
00011111

Sample Outputs:
y
(y|z)&x
!x
x|y&z

Solution (Python):
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])

Solution (Python):
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)])
exit(0)
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):
    global 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))

Solution (Python):
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()])