Multiplique por 2, divida por 6

Você recebe um número inteiro $n$. Em um movimento, você pode multiplicar $n$ por $2$ ou dividir $n$ por $6$ , se $n$ for múltiplo de $6$. Sua tarefa é encontrar o número mínimo de movimentos necessários para obter $1$ a partir de $n$ ou determinar se é impossível fazer isso. Você precisa responder a casos de teste independentes.

Entrada:

A primeira linha da entrada contém um número inteiro $t$, o número de casos de teste. Em seguida, seguem os $t$ casos de teste. A única linha de cada caso de teste contém um número inteiro $n$.

Saída:

Para cada caso de teste, imprima o número mínimo de movimentos necessários para obter $1$ a partir de $n$ se for possível fazer isso ou $-1$ se for impossível obter $1$ de $n$.

Restrições:

• $1 \leq t \leq 2*10^4$
• $1 \leq n \leq 10^9$

Exemplos:

7
1
2
3
12
12345
15116544
387420489

Nota:

Considere o sexto caso de teste do exemplo. A resposta pode ser obtida pela seguinte sequência de movimentos do número inteiro fornecido $n = 15116544$:

1. Divida por $6$ e obtenha $2519424$;
2. divida por $6$ e obtenha $419904$;
3. divida por $6$ e obtenha $69984$;
4. divida por $6$ e obtenha $11664$;
5. multiplique por $2$ e obtenha $23328$;
6. divida por $6$ e obtenha $3888$;
7. divida por $6$ e obtenha $648$;
8. divida por $6$ e obtenha $108$;
9. multiplique por $2$ e obtenha $216$;
10. divida por $6$ e obtenha $36$;
11. divida por $6$ e obtenha $6$;
12. divida por $6$ e obtenha $1$.

Para submeter sua solução, use esse link