A. Дели!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано целое число $$$n$$$.

Вы можете выполнять любую из следующих операций над ним любое (возможно, нулевое) количество раз:

  1. Заменить $$$n$$$ на $$$\frac{n}{2}$$$, если $$$n$$$ делится на $$$2$$$;
  2. Заменить $$$n$$$ на $$$\frac{2n}{3}$$$, если $$$n$$$ делится на $$$3$$$;
  3. Заменить $$$n$$$ на $$$\frac{4n}{5}$$$, если $$$n$$$ делится на $$$5$$$.

Например, Вы можете заменить $$$30$$$ на $$$15$$$ при помощи первой операции, на $$$20$$$ при помощи второй операции или на $$$24$$$ при помощи третьей операции.

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

Вам необходимо ответить на $$$q$$$ независимых запросов.

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

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 1000$$$) — количество запросов.

Следующие $$$q$$$ строк содержат запросы. В каждом запросе задано целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

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

На каждый запрос выведите ответ на новой строке. Если невозможно получить $$$1$$$ из $$$n$$$, выведите -1. Иначе выведите минимальное количество операций, необходимое, чтобы сделать это.

Пример
Входные данные
7
1
10
25
30
14
27
1000000000000000000
Выходные данные
0
4
6
6
-1
6
72