Boolean Expression Compressor

You are asked to build a compressor for Boolean expressions that transforms expressions to the shortest form keeping their meaning.

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

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

Letters `a`, `b`, `c` and `d` represent Boolean variables that have values of either `0` or `1`. Operators are evaluated as shown in the Table below. In other words, `-` means negation (NOT), `^` means exclusive disjunction (XOR), and `*` means logical conjunction (AND).

Table: Evaluations of operators
<image>

Write a program that calculates the length of the shortest expression that evaluates equal to the given expression with whatever values of the four variables.

For example, `0`, that is the first expression in the sample input, cannot be shortened further. Therefore the shortest length for this expression is 1.

For another example, `(a*(1*b))`, the second in the sample input, always evaluates equal to `(a*b)` and `(b*a)`, which are the shortest. The output for this expression, thus, should be `5`.

Input

The input consists of multiple datasets. A dataset consists of one line, containing an expression conforming to the grammar described above. The length of the expression is less than or equal to 16 characters.

The end of the input is indicated by a line containing one `.` (period). The number of datasets in the input is at most 200.

Output

For each dataset, output a single line containing an integer which is the length of the shortest expression that has the same value as the given expression for all combinations of values in the variables.

Sample Input


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


Output for the Sample Input


1
5
2
1
13






Example

Input

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


Output

1
5
2
1
13

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
from heapq import heappush, heappop
base = [a, b, c, d, e, 0]
Q = [(1, el) for el in base]
L = {el: 1 for el in base}
H = []
get = L.get
push = H.append
while Q:
	(l, p) = heappop(Q)
	if L[p] < l:
		continue
	if l + 1 < get(p ^ e, 17):
		L[p ^ e] = l + 1
		if l + 1 < 16:
			heappush(Q, (l + 1, p ^ e))
	if l + 3 < 16:
		for (q, r) in H:
			if l + r + 3 <= 16:
				if l + r + 3 < get(p & q, 17):
					L[p & q] = l + r + 3
					if l + r + 3 < 16:
						heappush(Q, (l + r + 3, p & q))
				if l + r + 3 < get(p ^ q, 17):
					L[p ^ q] = l + r + 3
					if l + r + 3 < 16:
						heappush(Q, (l + r + 3, p ^ q))
			else:
				break
	if l < 7:
		push((p, l))
print(*map(L.__getitem__, eval('e&%s' % ',e&'.join(open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]))), sep='\n')


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
QS = [[] for i in range(17)]
QS[1] = [a, b, c, d]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
for l in range(1, 16):
	Q = QS[l]
	li = 13 - l
	l3 = l + 3
	l1 = l + 1
	pop = Q.pop
	pushQN = QS[l1].append
	while Q:
		p = pop()
		if L[p] < l:
			continue
		if l < 13:
			if l1 < get(p ^ e, 17):
				L[p ^ e] = l1
				pushQN(p ^ e)
			for (q, r) in H:
				if r < li:
					if l3 + r < get(p & q, 17):
						L[p & q] = l3 + r
						QS[l3 + r].append(p & q)
					if l3 + r < get(p ^ q, 17):
						L[p ^ q] = l3 + r
						QS[l3 + r].append(p ^ q)
				elif r == li:
					if p & q not in L:
						L[p & q] = 16
					if p ^ q not in L:
						L[p ^ q] = 16
				else:
					break
			l < 7 and push((p, l))
		elif l1 < get(p ^ e, 17):
			L[p ^ e] = l1
print(*map(L.__getitem__, eval('e&' + ',e&'.join(open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]))), sep='\n')


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
from heapq import heappush, heappop
base = [a, b, c, d, e, 0]
Q = [(1, el) for el in base]
L = {el: 1 for el in base}
H = []
while Q:
	(l, p) = heappop(Q)
	if L[p] < l:
		continue
	if l + 1 < L.get(p ^ e, 17):
		L[p ^ e] = l + 1
		if l + 1 < 16:
			heappush(Q, (l + 1, p ^ e))
	if l + 3 < 16:
		for (q, r) in H:
			if l + r + 3 <= 16:
				if l + r + 3 < L.get(p & q, 17):
					L[p & q] = l + r + 3
					if l + r + 3 < 16:
						heappush(Q, (l + r + 3, p & q))
				if l + r + 3 < L.get(p ^ q, 17):
					L[p ^ q] = l + r + 3
					if l + r + 3 < 16:
						heappush(Q, (l + r + 3, p ^ q))
			else:
				break
	if l < 7:
		H.append((p, l))
print(*map(L.__getitem__, eval('e&%s' % ',e&'.join(open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]))), sep='\n')


def calc(s):

	def parse(a, b, c, d):
		nonlocal cur
		g = s[cur]
		cur += 1
		if g == '-':
			return 1 ^ parse(a, b, c, d)
		if g == '(':
			p = parse(a, b, c, d)
			cmd = s[cur]
			cur += 1
			q = parse(a, b, c, d)
			cur += 1
			return p ^ q if cmd == '^' else p & q
		return eval(g)
	res = 0
	for b in range(16):
		cur = 0
		if parse(*map(int, format(b, '04b'))):
			res += 1 << b
	return res
base = 'abcd10'
L = {}
for e in base:
	state = calc(e)
	L[state] = 1
ALL = 2 ** 16 - 1
MAX = 10 ** 18
for i in range(6):
	R = dict(L)
	for p in R:
		if R[p] < 16:
			L[p ^ ALL] = min(L.get(p ^ ALL, MAX), R[p] + 1)
		if R[p] + 3 < 16:
			for q in R:
				if R[p] + R[q] + 3 <= 16:
					L[p & q] = min(L.get(p & q, MAX), R[p] + R[q] + 3)
					L[p ^ q] = min(L.get(p ^ q, MAX), R[p] + R[q] + 3)
while 1:
	s = input()
	if s == '.':
		break
	print(L[calc(s)])


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
QS = [[] for i in range(17)]
QS[1] = [a, b, c, d]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
for l in range(1, 16):
	Q = QS[l]
	li = 13 - l
	l3 = l + 3
	l1 = l + 1
	pop = Q.pop
	pushQN = QS[l1].append
	while Q:
		p = pop()
		if L[p] < l:
			continue
		if l1 < get(p ^ e, 17):
			L[p ^ e] = l1
			l < 12 and pushQN(p ^ e)
		if l < 13:
			for (q, r) in H:
				if r < li:
					if l3 + r < get(p & q, 17):
						L[p & q] = l3 + r
						QS[l3 + r].append(p & q)
					if l3 + r < get(p ^ q, 17):
						L[p ^ q] = l3 + r
						QS[l3 + r].append(p ^ q)
				elif r == li:
					if p & q not in L:
						L[p & q] = 16
					if p ^ q not in L:
						L[p ^ q] = 16
				else:
					break
			if l < 7:
				push((p, l))
print(*map(L.__getitem__, eval('e&' + ',e&'.join(open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]))), sep='\n')


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
from heapq import heappush, heappop
base = [a, b, c, d, e, 0]
Q = [(1, el) for el in base]
L = {el: 1 for el in base}
H = []
while Q:
	(l, p) = heappop(Q)
	if L[p] < l:
		continue
	if l + 1 < L.get(p ^ e, 17):
		L[p ^ e] = l + 1
		if l + 1 < 16:
			heappush(Q, (l + 1, p ^ e))
	if l + 3 < 16:
		for (q, r) in H:
			if l + r + 3 <= 16:
				if l + r + 3 < L.get(p & q, 17):
					L[p & q] = l + r + 3
					if l + r + 3 < 16:
						heappush(Q, (l + r + 3, p & q))
				if l + r + 3 < L.get(p ^ q, 17):
					L[p ^ q] = l + r + 3
					if l + r + 3 < 16:
						heappush(Q, (l + r + 3, p ^ q))
			else:
				break
	if l < 7:
		H.append((p, l))
print(*(L[e & eval(s)] for s in open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]), sep='\n')


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
QS = [[] for i in range(17)]
QS[1] = [a, b, c, d]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
for l in range(1, 16):
	Q = QS[l]
	QN = QS[l + 1]
	while Q:
		p = Q.pop()
		if L[p] < l:
			continue
		if l + 1 < get(p ^ e, 17):
			L[p ^ e] = l + 1
			l < 15 and QN.append(p ^ e)
		if l < 13:
			li = 13 - l
			l3 = 3 + l
			for (q, r) in H:
				if r < li:
					k = p & q
					if r < get(k, 17) - l3:
						L[k] = l3 + r
						QS[l3 + r].append(k)
					k = p ^ q
					if r < get(k, 17) - l3:
						L[k] = l3 + r
						QS[l3 + r].append(k)
				elif r == li:
					if p & q not in L:
						L[p & q] = 16
					if p ^ q not in L:
						L[p ^ q] = 16
				else:
					break
		if l < 7:
			push((p, l))
print(*map(L.__getitem__, eval('e&' + ',e&'.join(open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]))), sep='\n')


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535

def calc(s):
	res = eval(s.replace('-', '~').replace('*', '&').replace('1', 'e'))
	return e ^ ~res if res < 0 else res
base = [a, b, c, d, e, 0]
L = {el: 1 for el in base}
for i in range(6):
	R = dict(L)
	for p in R:
		if R[p] < 16:
			L[p ^ e] = min(L.get(p ^ e, 16), R[p] + 1)
		if R[p] + 3 < 16:
			for q in R:
				if R[p] + R[q] + 3 <= 16:
					L[p & q] = min(L.get(p & q, 16), R[p] + R[q] + 3)
					L[p ^ q] = min(L.get(p ^ q, 16), R[p] + R[q] + 3)
while 1:
	s = input()
	if s == '.':
		break
	print(L[calc(s)])


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
L = {el: 1 for el in [a, b, c, d, e, 0]}
for i in range(6):
	R = sorted(L.items(), key=lambda x: x[1])
	for (p, l) in R:
		if l < 16:
			L[p ^ e] = min(L.get(p ^ e, 16), l + 1)
			if l + 3 < 16:
				for (q, r) in R:
					if l + r + 3 <= 16:
						L[p & q] = min(L.get(p & q, 16), l + r + 3)
						L[p ^ q] = min(L.get(p ^ q, 16), l + r + 3)
					else:
						break
		else:
			break
print(*(L[e & eval(s)] for s in open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]), sep='\n')


a = 65280
b = 61680
c = 52428
d = 43690
e = 65535
from heapq import heappush, heappop
Q = [(1, a), (1, b), (1, c), (1, d)]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
while Q:
	(l, p) = heappop(Q)
	if L[p] < l:
		continue
	if l + 1 < get(p ^ e, 17):
		L[p ^ e] = l + 1
		l < 15 and heappush(Q, (l + 1, p ^ e))
	if l < 13:
		li = 13 - l
		l3 = 3 + l
		for (q, r) in H:
			if r <= li:
				k = p & q
				if r < get(k, 17) - l3:
					L[k] = l3 + r
					r < li and heappush(Q, (l3 + r, k))
				k = p ^ q
				if r < get(k, 17) - l3:
					L[k] = l3 + r
					r < li and heappush(Q, (l3 + r, k))
			else:
				break
	if l < 7:
		push((p, l))
print(*map(L.__getitem__, eval('e&' + ',e&'.join(open(0).read().replace(*'-~').replace(*'*&').replace(*'1e').split()[:-1]))), sep='\n')