Divide it! (Codeforces 1176A)
Tags: Greedy, brute force

You are given an integer $$$n$$$.You can perform any of the following operations with this number an arbitrary (possibly, zero) number of times:   Replace $$$n$$$ with $$$\frac{n}{2}$$$ if $$$n$$$ is divisible by $$$2$$$;  Replace $$$n$$$ with $$$\frac{2n}{3}$$$ if $$$n$$$ is divisible by $$$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 Inputs:
7
1
10
25
30
14
27
1000000000000000000

Sample Outputs:
0
4
6
6
-1
6
72

Solution (Python):
def i():
    n = int(input())
    c = 0
    tp = [5, 3, 2, 1]
    while n != 1:
        if n % tp[0] == 0:
            n //= tp[0]
            c += tp[1]
        else:
            if tp[1] == 1:
                return '-1'
            tp.pop(0)
    return str(c)
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
def i():
    n = int(input())
    c = 0
    while n != 1:
        if n % 5 == 0:
            n //= 5
            c += 3
        elif n % 3 == 0:
            n //= 3
            c += 2
        elif n % 2 == 0:
            n //= 2
            c += 1
        else:
            return '-1'
    return str(c)
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
a = ((2, 1), (3, 2), (5, 3))
for _ in [0] * int(input()):
    n = int(input())
    i = 0
    for (x, y) in a:
        while n % x == 0:
            n //= x
            i += y
    print((i, -1)[n > 1])