Codeforces Round 565 (Div. 3) |
---|
Finished |
You are given an integer $$$n$$$.
You can perform any of the following operations with this number an arbitrary (possibly, zero) number of times:
For example, you can replace $$$30$$$ with $$$15$$$ using the first operation, with $$$20$$$ using the second operation or with $$$24$$$ using the third operation.
Your task is to find the minimum number of moves required to obtain $$$1$$$ from $$$n$$$ or say that it is impossible to do it.
You have to answer $$$q$$$ independent queries.
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of queries.
The next $$$q$$$ lines contain the queries. For each query you are given the integer number $$$n$$$ ($$$1 \le n \le 10^{18}$$$).
Print the answer for each query on a new line. If it is impossible to obtain $$$1$$$ from $$$n$$$, print -1. Otherwise, print the minimum number of moves required to do it.
7 1 10 25 30 14 27 1000000000000000000
0 4 6 6 -1 6 72
Name |
---|