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