Вам дано целое число \(n\). За один ход вы можете или умножить \(n\) на 2, или разделить \(n\) на \(6\) (если оно делится на \(6\) без остатка).
Ваша задача — найти минимальное количество ходов, необходимое, чтобы получить \(1\) из \(n\) или определить, что это невозможно.
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ на него — минимальное количество ходов, необходимое, чтобы получить \(1\) из \(n\), если это возможно, или -1, если невозможно получить \(1\) из \(n\).
Примечание
Рассмотрим шестой набор тестовых данных примера. Ответ может быть получен следующей последовательностью ходов из заданного числа \(15116544\):
- Разделим на \(6\) и получим \(2519424\);
- разделим на \(6\) и получим \(419904\);
- разделим на \(6\) и получим \(69984\);
- разделим на \(6\) и получим \(11664\);
- умножим на \(2\) и получим \(23328\);
- разделим на \(6\) и получим \(3888\);
- разделим на \(6\) и получим \(648\);
- разделим на \(6\) и получим \(108\);
- умножим на \(2\) и получим \(216\);
- разделим на \(6\) и получим \(36\);
- разделим на \(6\) и получим \(6\);
- разделим на \(6\) и получим \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
2
3
12
12345
15116544
387420489
|
0
-1
2
-1
-1
12
36
|