Matemàtic frustrat P50129

Considereu el passatemps següent: Començant amb el nombre 0, a cada pas podeu decidir entre multiplicar el nombre actual per 3 o sumar-li 1. El joc s’acaba quan aconseguiu un nombre objectiu $n$. Quin és el mínim nombre de passos per arribar-hi?

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i $10^9$.

Sortida

Escriviu el mínim nombre de passos per a cada $n$ donada.