#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
int MOD = 10;
const long double E = 1e-9;
unsigned char ccc;
bool _minus = false;
template <typename T>
inline T sqr(T t) {
  return (t * t);
}
inline void read(long long &n) {
  n = 0;
  _minus = false;
  while (true) {
    ccc = getchar();
    if (ccc == ' ' || ccc == '\n') break;
    if (ccc == '-') {
      _minus = true;
      continue;
    }
    n = n * 10 + ccc - '0';
  }
  if (_minus) n *= -1;
}
inline bool read(int &n) {
  n = 0;
  _minus = false;
  while (true) {
    ccc = getchar();
    if (ccc == ' ' || ccc == '\n') {
      if (ccc == '\n') return true;
      break;
    }
    if (ccc == '-') {
      _minus = true;
      continue;
    }
    n = n * 10 + ccc - '0';
  }
  if (_minus) n *= -1;
  return false;
}
char wwww[19];
int kkkk;
inline void write(long long y) {
  long long x = y;
  kkkk = 0;
  if (x < 0) {
    putchar('-');
    x *= -1;
  }
  if (!x) {
    ++kkkk;
    wwww[kkkk] = '0';
  } else
    while (x) {
      ++kkkk;
      wwww[kkkk] = char(x % 10 + '0');
      x /= 10;
    }
  for (int i = kkkk; i >= 1; --i) putchar(wwww[i]);
}
const int MAX = (1 << 8);
string ar[MAX];
const int MAX_LEN = 29;
vector<pair<string, int> > e[MAX_LEN], t[MAX_LEN], f[MAX_LEN];
int used[MAX];
void print(int n) {
  for (int i = 0; i < 8; i++) {
    cout << n % 2;
    n /= 2;
  }
  cout << "\n";
}
string anses[1 << 8] = {"!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"};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  srand((unsigned int)time(NULL));
  cout.precision(10);
  cout << fixed;
  if (0) {
    if (0) {
      string s;
      cout << "string anses[1 << 8]={";
      while (cin >> s) {
        cout << '"' << s << '"' << ","
             << "\n";
      }
      cout << "}"
           << "\n";
      return 0;
    }
    int x = 0, y = 0, z = 0;
    for (int i = 0; i < 8; i++) {
      if ((i / 4)) {
        x |= (1 << i);
      }
      if ((i / 2) % 2) {
        y |= (1 << i);
      }
      if (i % 2) {
        z |= (1 << i);
      }
    }
    for (int i = 0; i < 8; i++) {
      if ((i / 4)) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << "\n";
    for (int i = 0; i < 8; i++) {
      if ((i / 2) % 2) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << "\n";
    for (int i = 0; i < 8; i++) {
      if (i % 2) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << "\n";
    f[1].push_back(make_pair("x", x));
    f[1].push_back(make_pair("y", y));
    f[1].push_back(make_pair("z", z));
    const int T = 14;
    for (int i = 1; i < MAX_LEN; i++) {
      for (auto tt : f[i]) {
        string s = tt.first;
        int ind = tt.second;
        if (ar[ind] == "" || (ar[ind].size() == s.size() && s < ar[ind])) {
          ar[ind] = s;
        }
        if (ar[ind].size() + 2 < s.size()) {
          continue;
        }
        if (i + 1 < MAX_LEN) {
          f[i + 1].push_back(make_pair("!" + s, (MAX - 1) ^ ind));
        }
        t[i].push_back(tt);
      }
      for (auto tt : t[i]) {
        string s = tt.first;
        int ind = tt.second;
        if (ar[ind] == "" || (ar[ind].size() == s.size() && s < ar[ind])) {
          ar[ind] = s;
        }
        if (ar[ind].size() + 2 < s.size()) {
          continue;
        }
        for (int j = 1; j <= i && i + j + 1 < MAX_LEN; j++) {
          for (auto v : f[j]) {
            if (ar[ind & v.second].size() == 0 ||
                ar[ind & v.second].size() + 2 < i + j + 1) {
              if (s < v.first)
                t[i + j + 1].push_back(
                    make_pair(s + "&" + v.first, ind & v.second));
              else
                t[i + j + 1].push_back(
                    make_pair(v.first + "&" + s, ind & v.second));
            }
          }
        }
        e[i].push_back(tt);
      }
      for (auto tt : e[i]) {
        string s = tt.first;
        int ind = tt.second;
        if (ar[ind] == "" || (ar[ind].size() == s.size() && s <= ar[ind])) {
          ar[ind] = s;
        }
        if (ar[ind].size() + 2 < s.size()) {
          continue;
        }
        assert((int)s.size() == i);
        for (int j = 1; j <= i && i + j + 1 < MAX_LEN; j++) {
          for (auto v : t[j]) {
            if (ar[ind | v.second].size() == 0 ||
                ar[ind | v.second].size() + 2 < i + j + 1) {
              if (s < v.first)
                e[i + j + 1].push_back(
                    make_pair(s + "|" + v.first, ind | v.second));
              else
                e[i + j + 1].push_back(
                    make_pair(v.first + "|" + s, ind | v.second));
            }
          }
        }
        if (i + 2 < MAX_LEN) {
          f[i + 2].push_back(make_pair("(" + s + ")", ind));
        }
      }
      bool ok = true;
      int u = 0;
      for (int i = 0; i < MAX; i++) {
        if (ar[i] == "") {
          ok = false;
        } else {
          u++;
        }
      }
      cout << "in " << i << " "
           << ((long double)u / ((long double)(1 << 8))) * 100 << "\n";
      if (ok) {
        cout << "break in " << i << "\n";
        break;
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < 8; i++) {
      if (s[i] == '1') {
        ans |= (1 << i);
      }
    }
    cout << anses[ans] << "\n";
  }
  if (0) {
    ofstream cout("output2.txt");
    cout << "string anses[1 << 8]={";
    for (int i = 0; i < MAX; i++) {
      if (i + 1 < MAX) {
        cout << '"' << ar[i] << '"' << ","
             << "\n";
      } else {
        cout << '"' << ar[i] << '"' << "};"
             << "\n";
      }
    }
    cout.close();
  }
}

### Prompt

Develop a solution in cpp to the problem described below:

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>

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
int MOD = 10;
const long double E = 1e-9;
unsigned char ccc;
bool _minus = false;
template <typename T>
inline T sqr(T t) {
  return (t * t);
}
inline void read(long long &n) {
  n = 0;
  _minus = false;
  while (true) {
    ccc = getchar();
    if (ccc == ' ' || ccc == '\n') break;
    if (ccc == '-') {
      _minus = true;
      continue;
    }
    n = n * 10 + ccc - '0';
  }
  if (_minus) n *= -1;
}
inline bool read(int &n) {
  n = 0;
  _minus = false;
  while (true) {
    ccc = getchar();
    if (ccc == ' ' || ccc == '\n') {
      if (ccc == '\n') return true;
      break;
    }
    if (ccc == '-') {
      _minus = true;
      continue;
    }
    n = n * 10 + ccc - '0';
  }
  if (_minus) n *= -1;
  return false;
}
char wwww[19];
int kkkk;
inline void write(long long y) {
  long long x = y;
  kkkk = 0;
  if (x < 0) {
    putchar('-');
    x *= -1;
  }
  if (!x) {
    ++kkkk;
    wwww[kkkk] = '0';
  } else
    while (x) {
      ++kkkk;
      wwww[kkkk] = char(x % 10 + '0');
      x /= 10;
    }
  for (int i = kkkk; i >= 1; --i) putchar(wwww[i]);
}
const int MAX = (1 << 8);
string ar[MAX];
const int MAX_LEN = 29;
vector<pair<string, int> > e[MAX_LEN], t[MAX_LEN], f[MAX_LEN];
int used[MAX];
void print(int n) {
  for (int i = 0; i < 8; i++) {
    cout << n % 2;
    n /= 2;
  }
  cout << "\n";
}
string anses[1 << 8] = {"!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"};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  srand((unsigned int)time(NULL));
  cout.precision(10);
  cout << fixed;
  if (0) {
    if (0) {
      string s;
      cout << "string anses[1 << 8]={";
      while (cin >> s) {
        cout << '"' << s << '"' << ","
             << "\n";
      }
      cout << "}"
           << "\n";
      return 0;
    }
    int x = 0, y = 0, z = 0;
    for (int i = 0; i < 8; i++) {
      if ((i / 4)) {
        x |= (1 << i);
      }
      if ((i / 2) % 2) {
        y |= (1 << i);
      }
      if (i % 2) {
        z |= (1 << i);
      }
    }
    for (int i = 0; i < 8; i++) {
      if ((i / 4)) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << "\n";
    for (int i = 0; i < 8; i++) {
      if ((i / 2) % 2) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << "\n";
    for (int i = 0; i < 8; i++) {
      if (i % 2) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << "\n";
    f[1].push_back(make_pair("x", x));
    f[1].push_back(make_pair("y", y));
    f[1].push_back(make_pair("z", z));
    const int T = 14;
    for (int i = 1; i < MAX_LEN; i++) {
      for (auto tt : f[i]) {
        string s = tt.first;
        int ind = tt.second;
        if (ar[ind] == "" || (ar[ind].size() == s.size() && s < ar[ind])) {
          ar[ind] = s;
        }
        if (ar[ind].size() + 2 < s.size()) {
          continue;
        }
        if (i + 1 < MAX_LEN) {
          f[i + 1].push_back(make_pair("!" + s, (MAX - 1) ^ ind));
        }
        t[i].push_back(tt);
      }
      for (auto tt : t[i]) {
        string s = tt.first;
        int ind = tt.second;
        if (ar[ind] == "" || (ar[ind].size() == s.size() && s < ar[ind])) {
          ar[ind] = s;
        }
        if (ar[ind].size() + 2 < s.size()) {
          continue;
        }
        for (int j = 1; j <= i && i + j + 1 < MAX_LEN; j++) {
          for (auto v : f[j]) {
            if (ar[ind & v.second].size() == 0 ||
                ar[ind & v.second].size() + 2 < i + j + 1) {
              if (s < v.first)
                t[i + j + 1].push_back(
                    make_pair(s + "&" + v.first, ind & v.second));
              else
                t[i + j + 1].push_back(
                    make_pair(v.first + "&" + s, ind & v.second));
            }
          }
        }
        e[i].push_back(tt);
      }
      for (auto tt : e[i]) {
        string s = tt.first;
        int ind = tt.second;
        if (ar[ind] == "" || (ar[ind].size() == s.size() && s <= ar[ind])) {
          ar[ind] = s;
        }
        if (ar[ind].size() + 2 < s.size()) {
          continue;
        }
        assert((int)s.size() == i);
        for (int j = 1; j <= i && i + j + 1 < MAX_LEN; j++) {
          for (auto v : t[j]) {
            if (ar[ind | v.second].size() == 0 ||
                ar[ind | v.second].size() + 2 < i + j + 1) {
              if (s < v.first)
                e[i + j + 1].push_back(
                    make_pair(s + "|" + v.first, ind | v.second));
              else
                e[i + j + 1].push_back(
                    make_pair(v.first + "|" + s, ind | v.second));
            }
          }
        }
        if (i + 2 < MAX_LEN) {
          f[i + 2].push_back(make_pair("(" + s + ")", ind));
        }
      }
      bool ok = true;
      int u = 0;
      for (int i = 0; i < MAX; i++) {
        if (ar[i] == "") {
          ok = false;
        } else {
          u++;
        }
      }
      cout << "in " << i << " "
           << ((long double)u / ((long double)(1 << 8))) * 100 << "\n";
      if (ok) {
        cout << "break in " << i << "\n";
        break;
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < 8; i++) {
      if (s[i] == '1') {
        ans |= (1 << i);
      }
    }
    cout << anses[ans] << "\n";
  }
  if (0) {
    ofstream cout("output2.txt");
    cout << "string anses[1 << 8]={";
    for (int i = 0; i < MAX; i++) {
      if (i + 1 < MAX) {
        cout << '"' << ar[i] << '"' << ","
             << "\n";
      } else {
        cout << '"' << ar[i] << '"' << "};"
             << "\n";
      }
    }
    cout.close();
  }
}

```