«Игра 23» — вот во что сейчас играет Поликарп. Изначально у него есть целое число \(n\) и его цель преобразовать его в целое число \(m\). За один ход он может умножить \(n\) на \(2\) или умножить \(n\) на \(3\). Он может совершать любое количество ходов.
Выведите количество ходов, сколько необходимо Поликарпу, чтобы получить из числа \(n\) число \(m\). Выведите -1, если это невозможно сделать.
Легко доказать, что любой способ преобразования из числа \(n\) в число \(m\) содержит одинаковое количество ходов (т.е. количество ходов не зависит от способа преобразования).
Выходные данные
Выведите количество ходов, чтобы получить из числа \(n\) число \(m\). Выведите -1, если это невозможно сделать.
Примечание
В первом примере одна из возможных последовательностей ходов: \(120 \rightarrow 240 \rightarrow 720 \rightarrow 1440 \rightarrow 4320 \rightarrow 12960 \rightarrow 25920 \rightarrow 51840.\) Всего совершено \(7\) ходов.
Во втором примере Поликарп не должен совершать ходы. Таким образом, ответ равен \(0\).
В третьем примере из \(48\) невозможно получить \(72\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
120 51840
|
7
|
|
2
|
42 42
|
0
|
|
3
|
48 72
|
-1
|