Codeforces Round 565 (Div. 3) |
---|
Закончено |
Вам задано целое число $$$n$$$.
Вы можете выполнять любую из следующих операций над ним любое (возможно, нулевое) количество раз:
Например, Вы можете заменить $$$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
Название |
---|