913_E. Logical Expression_36803
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 <image>, <image> and <image>.

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)&amp;x
!x
x|y&amp;z

Note

The truth table for the second function:

<image>
#include <bits/stdc++.h>
std::string E[300], T[300], F[300];
std::vector<int> EA, TA, FA;
bool cmp(const std::string &a, const std::string &b) {
  if (a.size() > b.size()) return true;
  if (a.size() < b.size()) return false;
  if (a > b) return true;
  return false;
}
int main() {
  std::ios::sync_with_stdio(0);
  for (int i = 0; i < 256; ++i) E[i] = T[i] = F[i] = std::string(100, '.');
  F[0x0f] = "x";
  F[0x33] = "y";
  F[0x55] = "z";
  EA.reserve(300);
  TA.reserve(300);
  FA.reserve(300);
  FA.push_back(0x0f);
  FA.push_back(0x33);
  FA.push_back(0x55);
  bool upd = true;
  while (upd) {
    upd = false;
    for (int i : FA)
      if (cmp(F[255 - i], "!" + F[i])) {
        if (F[255 - i].size() == 100) FA.push_back(255 - i);
        F[255 - i] = "!" + F[i], upd = true;
      }
    for (int i : EA)
      if (cmp(F[i], "(" + E[i] + ")")) {
        if (F[i].size() == 100) FA.push_back(i);
        F[i] = "(" + E[i] + ")", upd = true;
      }
    for (int i : TA)
      for (int j : FA)
        if (cmp(T[i & j], T[i] + "&" + F[j])) {
          if (T[i & j].size() == 100) TA.push_back(i & j);
          T[i & j] = T[i] + "&" + F[j], upd = true;
        }
    for (int i : FA)
      if (cmp(T[i], F[i])) {
        if (T[i].size() == 100) TA.push_back(i);
        T[i] = F[i], upd = true;
      }
    for (int i : EA)
      for (int j : TA)
        if (cmp(E[i | j], E[i] + "|" + T[j])) {
          if (E[i | j].size() == 100) EA.push_back(i | j);
          E[i | j] = E[i] + "|" + T[j], upd = true;
        }
    for (int i : TA)
      if (cmp(E[i], T[i])) {
        if (E[i].size() == 100) EA.push_back(i);
        E[i] = T[i], upd = true;
      }
  }
  int N;
  std::cin >> N;
  for (int i = 0; i < N; ++i) {
    std::string str;
    std::cin >> str;
    int ans = 0;
    for (int i = 0; i < 8; ++i)
      if (str[i] == '1')
        ans = ans * 2 + 1;
      else
        ans = ans * 2;
    std::cout << E[ans] << std::endl;
  }
}

4
00110011
00000111
11110000
00011111
 4
11000010
11000010
11001110
10001001
 1
11001110
 2
11001110
01001001
 5
01111000
00110110
00011100
01110111
01010011
 3
10001001
10111011
10111101
 4
00110011
00000111
11110000
00011111
 4
11000010
11000000
11001110
10001001
 1
01001110
 2
11001110
01001000
 5
01111000
00110110
00011100
01110111
01010010
 3
10001011
10111011
10111101
 4
00110011
00000111
11110000
00011110
 4
00110011
10000111
11110000
00011111
 4
11000010
01000000
11001110
10001001
 1
11000110
 2
01001110
01001000
 5
01111000
00110110
00011000
01110111
01010010
 3
10001011
10011011
10111101
 4
00110011
00000111
11100000
00011110
 4
00110011
10001111
11110000
00011111
 4
10000010
01000000
11001110
10001001
 1
10000110
 2
01001110
01101000
 5
01111000
00110010
00011000
01110111
01010010
 3
10001011
10011011
10111111
 4
00110011
00000111
11100000
00011010
 4
00110011
10001111
11110000
00011011
 4
10000010
01000000
11001111
10001001
 1
10000111
 2
01101110
01101000
 5
01111000
00100010
00011000
01110111
01010010
 3
10001011
10111011
10111111
 4
00110011
00000111
11100000
00001010
 4
00110011
10001111
11110000
00010011
 4
10000010
11000000
11001111
10001001
 1
10001111
 2
11101110
01101000
 5
01111000
00100010
00011000
01110111
01000010
 3
10001011
10111011
10110111
 4
00110011
00000111
11100010
00001010
 4
00110001
10001111
11110000
00010011
 4
10000010
11000000
11001111
10101001
 1
10001101
 2
10101110
01101000
 5
00111000
00100010
00011000
01110111
01000010
 3
10001011
10011011
10110111
 4
00110011
00000111
11100010
10001010
 4
00110001
10001111
11110010
00010011
 4
10000010
11000000
11001111
00101001
 1
10101101
 2
10101111
01101000
 5
00111000
00100010
00011000
01110111
00000010
 3
10001011
10011011
10010111
 4
00110011
00010111
11100010
10001010

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