Botas es un muchacho a quien le gusta mucho los números en especial el numero uno (por que el sueña ser algún día el número uno en programación). Botas elije un número entero positivo y en el puede realizar una de las tres siguientes operaciones:

Restarle 1. (n = n −1)

Si es divisible entre 2, dividirlo entre 2. (n = n/2)

Si es divisible entre 3, dividirlo entre 3. (n = n/3)

Ahora la pregunta es, dado un entero n, encontrar el mínimo número de operaciones para llegar al número 1.

La primera línea contiene un numero T (1 ≤T ≤10⁵), que representa el número de casos de prueba. Cada una de las T siguientes líneas contiene un entero n (1 ≤n ≤1000) el numero elegido por Botas;

Imprimir en una línea el mínimo número de operaciones requeridas para llegar a 1.

Fe de erratas del ejemplo histórico: se corrigieron las respuestas de 10 y 9 a 3 y 2, respectivamente, para cumplir el mínimo de operaciones solicitado expresamente en el enunciado. El PDF original se conserva sin cambios.