Binario en decimal
Cuando a Ann Osen Tera le explicaron los números binarios lo entendió todo mal. En clase, su profesor les dijo que con ellos se podía representar cualquier número usando únicamente los dígitos 0 y 1. También oyó que había sumas y multiplicaciones por algún lado, y con esas frases sueltas se hizo su propia idea de lo que eran.
Y lo que pasó era de esperar. Cuando llegó el día del examen y el profesor les pidió que convirtieran a binario varios números escritos en decimal, Ann dio una respuesta completamente disparatada:
2 = 1 + 1
6 = (1 + 1 + 1) * (1 + 1)
24 = 1 + 11 + 11 + 1
120 = 110 + 10
Ann pensaba que pasar un número a binario significaba ¡escribir una expresión de sumas y multiplicaciones de números que solo tuvieran los dígitos 0 y 1! Así por ejemplo, para escribir el 12 lo que hacía sería sumar 1 y 11.
Lo peor de todo es que aunque la respuesta estaba completamente mal, contestarla le costó mucho tiempo porque buscaba la expresión con el menor número de operaciones, y eso no siempre era fácil.
Entrada
La entrada estándar contendrá una sucesión de números, en decimal, entre 1 y 10.000 terminada por un 0, que no deberá procesarse.
El programa deberá ser capaz de procesar, en una sola ejecución, un considerable número de casos.
Salida
Por cada número de la entrada, el programa escribirá el menor número de operaciones que tendrá la "representación en binario" entendida por Ann. Si un número ya está "en binario" (solo tiene dígitos 0 y 1) se escribirá 0.
Entrada de ejemplo
2 6 24 1111 0
Salida de ejemplo
1 4 3 0