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.