Preparing NOJ

# Divide it!

1000ms 262144K

## Description:

You are given an integer $n$.

You can perform any of the following operations with this number an arbitrary (possibly, zero) number of times:

1. Replace $n$ with $\frac{n}{2}$ if $n$ is divisible by $2$;
2. Replace $n$ with $\frac{2n}{3}$ if $n$ is divisible by $3$;
3. Replace $n$ with $\frac{4n}{5}$ if $n$ is divisible by $5$.

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.

## Input:

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}$).

## Output:

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.

## Sample Input:

 7 1 10 25 30 14 27 1000000000000000000

## Sample Output:

 0 4 6 6 -1 6 72

Info

Provider CodeForces

Code CF1176A

Tags

brute forcegreedyimplementation

Submitted 136

Passed 82

AC Rate 60.29%

Date 07/21/2019 13:41:28

Related

Nothing Yet