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.


-----Example-----
Input
7
1
10
25
30
14
27
1000000000000000000

Output
0
4
6
6
-1
6
72

Difficulty: introductory

Starter code:

Solutions:
for i in range(int(input())):
    
    n=int(input())
    moves=0
    while n%2==0:
        n=n//2
        moves+=1
    while n%3==0:
        n=n//3
        moves+=2
    while n%5==0:
        n=n//5
        moves+=3
    if n==1:
        print(moves)
    else :
        print(-1)

#!/usr/bin/env python
for _ in range(int(input())):
    n = int(input())
    a, b, c = 0, 0, 0
    while n % 2 == 0:
        a += 1
        n //= 2
    while n % 3 == 0:
        a += 1
        b += 1
        n //= 3
    while n % 5 == 0:
        a += 2
        c += 1
        n //= 5
    if n > 1:
        print(-1)
    else:
        print(a + b + c)


q = int(input())
for i in range(q):
    n = int(input())
    num = 0
    while n % 2 == 0:
        num += 1
        n //= 2
    while n % 3 == 0:
        num += 2
        n //= 3
    while n % 5 == 0:
        num += 3
        n //= 5

    if n == 1:
        print(num)
    else:
        print(-1)

def main():
    q = int(input())
    for i in range(q):
        t = int(input())
        ans = 0
        while t % 5 == 0:
            t = (4 * t) // 5
            ans += 1
        while t % 3 == 0:
            t = (2 * t) // 3
            ans += 1
        while t % 2 == 0:
            t //= 2
            ans += 1
        if t != 1:
            print(-1)
        else:
            print(ans)


main()


def solve(n):
	c = 0
	if n == 1:
		return c
	while n != 1:
		if n%2 == 0:
			n //= 2
		elif n%3 == 0:
			n = 2*n//3
		elif n%5 == 0:
			n = 4*n//5
		else:
			return -1
		c += 1
	return c


for _ in range(int(input().strip())):
	n = int(input().strip())
	print(solve(n))



q = int(input())
for _ in range(q):
    n = int(input())
    c = 0
    while n > 1:
        c += 1
        if n % 2 == 0:
            n //= 2
        elif n % 3 == 0:
            n = (n // 3) * 2
        elif n % 5 == 0:
            n = (n // 5) * 4
        else:
            break
    if n == 1:
        print(c)
    else:
        print(-1)


# @author 

import sys


class ADivideIt:
    def solve(self):
        for _ in range(int(input())):
            n = int(input())
            cnt = 0
            while n != 1:
                if n % 2 == 0:
                    n //= 2
                elif n % 3 == 0:
                    n //= 3
                    n *= 2
                elif n % 5 == 0:
                    n *= 4
                    n //= 5
                else:
                    print(-1)
                    break
                cnt += 1
            else:
                print(cnt)




solver = ADivideIt()
input = sys.stdin.readline

solver.solve()


def f(n):
    s=0
    while n%2==0:
        n//=2
        s+=1
    while n%3==0:
        n//=3
        s+=2
    while n%5==0:
        n//=5
        s+=3
    if n!=1:
        return -1
    else:
        return s
for k in range(int(input())):
    print(f(int(input())))


def ain():
    return map(int,input().split())
def lin():
    return list(ain())


def plist(l):
    for x in l:
        print(x, end= ' ')
    print()

def indexof(l,v,l3):
    return l3[v]


for _ in range(int(input())):
    n = int(input())
    c = 0
    f=  0
    while n != 1:
        if n%2 == 0:
            n =n //2
        elif n%3 == 0:
            n = (2*n)//3
        elif n%5 == 0:
            n = (4*n) //5
        else:
            f = 1
            print(-1)
            break
        c+=1
    if f == 0:
        print(c)




q = int(input())
for q in range(q):
    n = int(input())
    ans = 0
    while (n != 1):
        if n % 5 == 0:
            n = n // 5 * 4
        elif n % 3 == 0:
            n = n // 3 * 2
        elif n & 1 == 0:
            n >>= 1
        else:
            break
        ans += 1
    if n != 1:
        print(-1)
    else:
        print(ans)


def calc(n):
    re = 0
    while n % 5 == 0:
        n = n//5*4
        re += 1
    while n % 3 == 0:
        n = n//3*2
        re += 1
    while n % 2 == 0:
        n = n//2
        re += 1
    if n == 1:
        return re
    else:
        return -1

Q = int(input())
for _ in range(Q):
    print(calc(int(input())))


q = int(input())
for i in range(q):
    n = int(input())
    ops = 0
    while not n%2:
        n = n//2
        ops += 1
    while not n%3:
        n = n//3
        ops += 2
    while not n%5:
        n = n//5
        ops += 3
    print(-1 if n>1 else ops)


def solve(n):
    p2, p3, p5 = 0, 0, 0
    while n % 2 == 0:
        n //= 2;
        p2 += 1
    while n % 3 == 0:
        n //= 3
        p3 += 1
    while n % 5 == 0:
        n //= 5
        p5 += 1
    if n != 1:
        return -1
    return 2 * p3 + 3 * p5 + p2

q = int(input())
for i in range(q):
    n = int(input())
    print(solve(n))

q = int(input())
for _ in range(q):
    n = int(input())
    ans = 0
    while n % 5 == 0:
        ans += 3
        n //= 5
    while n % 3 == 0:
        ans += 2
        n //= 3
    while n % 2 == 0:
        ans += 1
        n //= 2
    if n != 1:
        print(-1)
    else:
        print(ans)

    


n = int(input())
for i in range(n):
    q = int(input())
    s = 0
    while(q%5==0):
        q = q//5
        s+=3
    while(q%3==0):
        q = q//3
        s+=2
    while(q%2==0):
        q = q//2
        s+=1
    if(q==1):
        print(s)
    else:
        print(-1)


def fix(a):
    c = 0
    while a != 1:
        if a % 2 == 0:
            a = a // 2
            c += 1
        elif a % 3 == 0:
            a = 2 * a // 3
            c += 1
        elif a % 5 == 0:
            a = 4 * a // 5
            c += 1
        else:
            return -1
    return c

def go():
    q = int(input())
    o = ''
    for i in range(q):
        o += str(fix(int(input()))) + '\n'
    return o

print(go())


q = int(input())
for i in range(q):
    n = int(input())
    ans = 0
    while n % 2 == 0:
        n //= 2
        ans += 1
    while n % 3 == 0:
        n //= 3
        ans += 2
    while n % 5 == 0:
        n //= 5
        ans += 3
    if n == 1:
        print(ans)
    else:
        print(-1)

for i in range(int(input())):
    n = int(input()) 
    cnt = 0
    while n > 1:
        cnt += 1
        if n % 2 == 0:
            n //= 2
        elif n % 3 == 0:
            n = 2 * n // 3
        elif n % 5 == 0:
            n = 4 * n // 5
        else:
            cnt = -1
            break
    print(cnt) 
            


n = int(input())
for i in range(n):
    x = int(input())
    k = 0
    while x != 1:
        if x % 2 == 0:
            x = x // 2
            k += 1
        elif x % 3 == 0:
            x = x - x// 3
            k += 1
        elif x % 5 == 0:
            x = x - x // 5
            k+= 1
        else:
            k = -1
            break
    print(k)

"""
NTC here
"""
from sys import setcheckinterval,stdin
setcheckinterval(1000)

#print("Case #{}: {} {}".format(i, n + m, n * m))

iin=lambda :int(stdin.readline())
lin=lambda :list(map(int,stdin.readline().split()))

for _ in range(iin()):
    n=iin()
    ans=0
    while n!=1:
        ans+=1
        if n%2==0:
            n//=2
        elif n%3==0:
            n=2*(n//3)
        elif n%5==0:
            n=4*(n//5)
        else:
            print(-1)
            break
    else:
        print(ans)

q = int(input())

for _ in range(q):
    n = int(input())

    moves = 0

    while n % 5 == 0:
        moves += 1
        n = n // 5 * 4

    while n % 3 == 0:
        moves += 1
        n = n // 3 * 2
    while n % 2 == 0:
        moves += 1
        n //= 2

    if n == 1:
        print(moves)
    else:
        print(-1)


q = int(input())

for t in range(q):
    n = int(input())
    ans = 0
    while n%5 == 0:
        n //= 5
        ans += 3
    while n%3 == 0:
        n //= 3
        ans += 2
    while n%2 == 0:
        n //= 2
        ans += 1
    if n == 1:
        print(ans)
    else:
        print(-1)

for i in range(int(input())):
    x = int(input())
    k = 0
    fl = True
    while fl:
        fl = x % 2 == 0 or x % 3 == 0 or x % 5 == 0
        if fl:
            if x % 2 == 0:
                while x % 2 == 0:
                    x //= 2
                    k += 1
            elif x % 3 == 0:
                x *= 2
                x //= 3
                k += 1
            elif x % 5 == 0:
                x *= 4
                x //= 5
                k += 1
    if x != 1:
        print(-1)
    else:
        print(k)