가장 짧은 논리식

닐스는 석사 논문을 준비하면서 자신이 만든 로그 시간 정지 문제 해결기의 소스 코드를 논문에 싣고 싶어 한다. 이 논문이 전 세계에서 수백만 부 인쇄될 것은 확실하므로, 환경에 주는 부담을 줄이려고 프로그램을 최대한 짧게 쓰려고 한다.

닐스를 도와 불 대수식을 최적화하는 프로그램을 작성하자. 입력으로는 괄호가 빠짐없이 붙은 식이 주어지고, 식은 한 글자짜리 연산자 &, |, ! 를 쓴다.

식마다 그 식과 논리적으로 같은 식 중 가장 짧은 것의 길이를 출력한다. 길이를 셀 때 공백은 세지 않는다.

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

이항 연산자에는 괄호가 반드시 붙는다. 그래서 이항 연산자 하나는 길이에 3을 더하고, ! 하나와 변수 하나는 각각 길이에 1을 더한다.

첫째 줄에 테스트 케이스의 개수 $n$이 주어진다 ($1 \le n \le 50$). 다음 $n$개 줄에는 위 문법을 따르는 식이 한 줄에 하나씩 주어진다. 각 식의 길이는 공백을 포함해 500자를 넘지 않는다.

테스트 케이스마다 같은 값을 내는 식 중 가장 짧은 것의 길이를 한 줄에 하나씩 출력한다.

첫 번째 예제의 식은 항상 거짓이다. 이 식은 (x & !x)로 쓸 수 있고, 길이는 6이다. 세 번째 예제는 드모르간 법칙을 두 번 적용하면 두 번째 예제와 같은 식이 된다.