Вам дано целое число \(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\).
Рассмотрим шестой набор тестовых данных примера. Ответ может быть получен следующей последовательностью ходов из заданного числа \(15116544\):
7 1 2 3 12 12345 15116544 387420489
0 -1 2 -1 -1 12 36
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач