Shortest Boolean Expression

Nils is preparing his master's thesis and wants to include the source code of his new logarithmic time halting problem solver. Millions of copies of the paper will be printed around the world, so he wants to write the program as short as possible to hold down the environmental cost.

Help Nils by writing an optimizer for boolean expressions. The input is a fully parenthesized expression built from the one character operators &, | and !.

For each expression, print the length of the shortest expression equivalent to it. Spaces are not counted.

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

Parentheses are required around every binary operator. A binary operator therefore adds three characters to the length, while one ! and one variable each add one character.

The first line has the number of test cases $n$ ($1 \le n \le 50$). Each of the next $n$ lines has one expression that follows the grammar above. No expression is longer than 500 characters, counting spaces.

For each test case, print the length of the shortest equivalent expression on its own line.

The expression in the first example is never true. It can be written as (x & !x), which has length 6. Applying De Morgan's law twice to the third example turns it into the second example.