Вам задано целое число \(n\).
Вы можете выполнять любую из следующих операций над ним любое (возможно, нулевое) количество раз:
- Заменить \(n\) на \(\frac{n}{2}\), если \(n\) делится на \(2\);
- Заменить \(n\) на \(\frac{2n}{3}\), если \(n\) делится на \(3\);
- Заменить \(n\) на \(\frac{4n}{5}\), если \(n\) делится на \(5\).
Например, Вы можете заменить \(30\) на \(15\) при помощи первой операции, на \(20\) при помощи второй операции или на \(24\) при помощи третьей операции.
Ваша задача — найти минимальное количество операций, необходимое для того, чтобы получить \(1\) из \(n\), или сказать, что это невозможно сделать.
Вам необходимо ответить на \(q\) независимых запросов.
Выходные данные
На каждый запрос выведите ответ на новой строке. Если невозможно получить \(1\) из \(n\), выведите -1. Иначе выведите минимальное количество операций, необходимое, чтобы сделать это.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
10
25
30
14
27
1000000000000000000
|
0
4
6
6
-1
6
72
|