Descenso mínimo

Te has encontrado un número $n$ ($1 \le n \le 10^{5}$). En cada operación, puedes hacer lo siguiente: - Restarle 1 a $n$ - Dividir $n$ entre 3 de manera exacta. ¿Cuál es el número mínimo de operaciones necesarias para convertir $n$ en $1$? ## Entrada En la primera línea aparece el número de casos de prueba. Cada caso de prueba está formado por una sola línea con el número $n$. ## Salida Por cada caso de prueba, imprime en una línea el número mínimo de operaciones necesarias para hacer que $n$ se convierta en $1$.

6
17
667
666
67
1
100000

6
11
10
7
0
19