Nils 正在准备他的硕士论文，并希望在其中包含他那套新的对数时间停机问题求解器的源代码。为了尽量减少他那篇革命性论文在全球范围内不可避免的数百万次打印所带来的环境影响，他希望尽可能缩短他的程序代码。

你需要通过设计一个布尔表达式优化器来帮助他。输入将是一个完全括号化的表达式，使用标准的单字符布尔运算符（&、| 和 !）。

对于每个表达式，请输出最短等价表达式的长度（不包含空格）。

expression ::= variable
             | ’(’ expression ’ ’ operator ’ ’ expression ’)’
             | ’!’ expression
operator ::= ’&’ | ’|’
variable ::= ’x’ | ’y’ | ’z’

特别注意，所有运算符都需要括号。这意味着每个运算符会为长度贡献三个字符，而取反（NOT）和变量引用各贡献一个字符。

输入格式

输入包含 $1 \le n \le 50$ 组测试数据，其中 $n$ 由输入的第一行给出。每个测试用例由一行描述上述表达式的字符串给出。每个表达式的长度不超过 500 个字符（包含空格）。

输出格式

对于每个测试用例，输出最短等价表达式的长度。

说明

在样例中，第一个表达式永远为假。它可以写成 (x & !x)，其长度为 6。第三个样例可以通过两次应用德·摩根定律进行简化（简化后它等价于第二个样例）。

样例

输入格式 1

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

输出格式 1

6
9
9