Boolean Expression Compressor

Time limit2sMemory limit512 MB

Summary

Given a Boolean expression over four variables, find the length of the shortest equivalent expression using NOT, XOR, and AND.

Level: Medium7 of 10
Topics: Dynamic programming, Brute force, Bit manipulation, Implementation
Solved: No attempts yet

Problem

Build a compressor for Boolean expressions that rewrites an expression into the shortest form with the same meaning.

The grammar of the Boolean expressions has the terminals 0 1 a b c d - ^ * ( ), the start symbol <E>, and the following production rule:

<E> ::= 0 | 1 | a | b | c | d | -<E> | (<E>^<E>) | (<E>*<E>)

The letters a, b, c and d are Boolean variables whose value is either 0 or 1. The operators are evaluated as in the table below. - is negation (NOT), ^ is exclusive disjunction (XOR), and * is conjunction (AND).

x	y	`-x`	`(x^y)`	`(x*y)`
0	0	1	0	0
0	1	1	1	0
1	0	0	1	0
1	1	0	0	1

Table: evaluation of the operators

Write a program that computes the length of the shortest expression whose value equals the value of the given expression for every assignment of the four variables.

For example, 0 cannot be shortened any further, so its shortest length is 1. The expression (a*(1*b)) has the same value as (a*b) and as (b*a) for every assignment, and those two are the shortest, so the answer for it is 5.

Input

The input consists of several datasets. One dataset is one line holding an expression that follows the grammar above. The length of the expression is at most 16 characters.

The end of the input is a line holding a single period (.). The input holds at most 200 datasets.

Output

For each dataset, print one line with a single integer: the length of the shortest expression whose value equals the value of the given expression for every combination of values of the four variables.

Examples6

Example 1

Input

0
(a*(1*b))
(1^a)
(-(-a*-b)*a)
(a^(b^(c^d)))
.

Expected output

Example 2
Input
```
a
.
```
Expected output
```
1
```

Example 3

Input

0
1
a
b
c
d
-a
--a
---a
---------------a
-0
-1
--------0
.

Expected output

Example 4

Input

(a*-a)
(a^a)
(a^-a)
(a*a)
(a*1)
(a*0)
(a^0)
(a^1)
(1*1)
(0^0)
(1^1)
(0*1)
.

Expected output

Example 5

Input

(-(-a*-b)*a)
(-(-a*-b)^a)
-(-a*-b)
-(-a*-c)
(a*-(-a*-b))
-(--a*--b)
(-a^-b)
-(a^b)
.

Expected output

Example 6

Input

(a^(b^(c^d)))
((a^b)^(c^d))
(((a^b)^c)^d)
(a*(b*(c*d)))
((a*b)*(c*d))
(((a*b)*c)*d)
(a^(b*(c^d)))
.

Expected output