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

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
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

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"
)

-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 +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))