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:

   1) Restarle 1. ( $n = n-1$ ).

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

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

Ahora Botas se pregunta, dado un entero $n$, cual es el número mínimo de operaciones para llegar al número 1?.

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

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

 DP - BFS