B. Умножай на 2, дели на 6
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$. За один ход вы можете или умножить $$$n$$$ на 2, или разделить $$$n$$$ на $$$6$$$ (если оно делится на $$$6$$$ без остатка).

Ваша задача — найти минимальное количество ходов, необходимое, чтобы получить $$$1$$$ из $$$n$$$ или определить, что это невозможно.

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Единственная строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ на него — минимальное количество ходов, необходимое, чтобы получить $$$1$$$ из $$$n$$$, если это возможно, или -1, если невозможно получить $$$1$$$ из $$$n$$$.

Пример
Входные данные
7
1
2
3
12
12345
15116544
387420489
Выходные данные
0
-1
2
-1
-1
12
36
Примечание

Рассмотрим шестой набор тестовых данных примера. Ответ может быть получен следующей последовательностью ходов из заданного числа $$$15116544$$$:

  1. Разделим на $$$6$$$ и получим $$$2519424$$$;
  2. разделим на $$$6$$$ и получим $$$419904$$$;
  3. разделим на $$$6$$$ и получим $$$69984$$$;
  4. разделим на $$$6$$$ и получим $$$11664$$$;
  5. умножим на $$$2$$$ и получим $$$23328$$$;
  6. разделим на $$$6$$$ и получим $$$3888$$$;
  7. разделим на $$$6$$$ и получим $$$648$$$;
  8. разделим на $$$6$$$ и получим $$$108$$$;
  9. умножим на $$$2$$$ и получим $$$216$$$;
  10. разделим на $$$6$$$ и получим $$$36$$$;
  11. разделим на $$$6$$$ и получим $$$6$$$;
  12. разделим на $$$6$$$ и получим $$$1$$$.