Descripción

¡Eduardo ha creado un nuevo lenguaje de programación llamado Halk-E! Originalmente el lenguaje estaba pensado para que fuera uno de los lenguajes de programación más famosos y utilizados en un futuro. Lamentablemente debido al escaso tiempo que tiene Eduardo, el diseño de Halk-E fue bastante sencillo, tanto que solo contiene una variable, la ~X~. Para romper un poco lo estándar el valor por defecto de ~X~ es ~1~ para todos los programas de Halk-E. Además de la variable ~X~ el lenguaje contiene tres comandos principales:

• ADD: incrementa a ~X~ por ~3~. Es decir, ~X := X + 3~
• MUL: multiplica a ~X~ por ~2~. Es decir, ~X := X * 2~
• END: imprime ~X~ y finaliza el programa.

Eduardo se pregunta si podrá conseguir cualquier número entero usando su programa, además quisiera saber cuál es el mínimo número de operaciones que él necesita realizar para obtener un número dado. Como no tiene mucho tiempo disponible, te ha pedido ayuda para que resuelvas este interesante problema.

Entrada

La primera y única línea de la entrada contiene un entero ~N~, el número que se quiere obtener.

Salida

Imprima la mínima cantidad de operaciones necesarias para obtener el número ~N~. Si no hay forma de obtener el número ~N~ realizando las operaciones dadas, imprima ~0~.

Subtareas

• Subtarea 1: ~1 \le N \le 100~ (~21~ puntos)
• Subtarea 2: ~1 \le N \le 10^6~ (~37~ puntos)
• Subtarea 3: ~1 \le N \le 10^{18}~ (~42~ puntos)

Ejemplos

Entrada 1

10

Salida 1

4

Inicialmente ~X = 1~. Las operaciones a realizar son las siguientes:

• MUL: ~X := 1 * 2 = 2~
• ADD: ~X := 2 + 3 = 5~
• MUL: ~X := 5 * 2 = 10~
• END: imprime ~10~ y finaliza el programa.

Entrada 2

12

Salida 2

0