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

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)

print(*(L[e & eval(s)] for s in open(0).read().replace("-", "~").replace("*", "&").replace("1", "e").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
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)
print(
    *(
        L[e & eval(s)]
        for s in open(0)
        .read()
        .replace("-", "~")
        .replace("*", "&")
        .replace("1", "e")
        .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"
)

-base = [a, b, c, d, e, 0] -L = {el: 1 for el in base} +L = {el: 1 for el in [a, b, c, d, e, 0]} -    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) +    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 -        .replace("-", "~") -        .replace("*", "&") -        .replace("1", "e") +        .replace(*"-~") +        .replace(*"*&") +        .replace(*"1e")