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
[{"code": "for i in range(int(input())):\n    \n    n=int(input())\n    moves=0\n    while n%2==0:\n        n=n//2\n        moves+=1\n    while n%3==0:\n        n=n//3\n        moves+=2\n    while n%5==0:\n        n=n//5\n        moves+=3\n    if n==1:\n        print(moves)\n    else :\n        print(-1)", "passed": true, "time": 0.35, "memory": 14244.0, "status": "done"}, {"code": "#!/usr/bin/env python\nfor _ in range(int(input())):\n    n = int(input())\n    a, b, c = 0, 0, 0\n    while n % 2 == 0:\n        a += 1\n        n //= 2\n    while n % 3 == 0:\n        a += 1\n        b += 1\n        n //= 3\n    while n % 5 == 0:\n        a += 2\n        c += 1\n        n //= 5\n    if n > 1:\n        print(-1)\n    else:\n        print(a + b + c)\n", "passed": true, "time": 0.15, "memory": 14292.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    num = 0\n    while n % 2 == 0:\n        num += 1\n        n //= 2\n    while n % 3 == 0:\n        num += 2\n        n //= 3\n    while n % 5 == 0:\n        num += 3\n        n //= 5\n\n    if n == 1:\n        print(num)\n    else:\n        print(-1)", "passed": true, "time": 0.15, "memory": 14212.0, "status": "done"}, {"code": "def main():\n    q = int(input())\n    for i in range(q):\n        t = int(input())\n        ans = 0\n        while t % 5 == 0:\n            t = (4 * t) // 5\n            ans += 1\n        while t % 3 == 0:\n            t = (2 * t) // 3\n            ans += 1\n        while t % 2 == 0:\n            t //= 2\n            ans += 1\n        if t != 1:\n            print(-1)\n        else:\n            print(ans)\n\n\nmain()\n", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "def solve(n):\n\tc = 0\n\tif n == 1:\n\t\treturn c\n\twhile n != 1:\n\t\tif n%2 == 0:\n\t\t\tn //= 2\n\t\telif n%3 == 0:\n\t\t\tn = 2*n//3\n\t\telif n%5 == 0:\n\t\t\tn = 4*n//5\n\t\telse:\n\t\t\treturn -1\n\t\tc += 1\n\treturn c\n\n\nfor _ in range(int(input().strip())):\n\tn = int(input().strip())\n\tprint(solve(n))\n\n", "passed": true, "time": 0.15, "memory": 14320.0, "status": "done"}, {"code": "q = int(input())\nfor _ in range(q):\n    n = int(input())\n    c = 0\n    while n > 1:\n        c += 1\n        if n % 2 == 0:\n            n //= 2\n        elif n % 3 == 0:\n            n = (n // 3) * 2\n        elif n % 5 == 0:\n            n = (n // 5) * 4\n        else:\n            break\n    if n == 1:\n        print(c)\n    else:\n        print(-1)\n", "passed": true, "time": 0.14, "memory": 14264.0, "status": "done"}, {"code": "# @author \n\nimport sys\n\n\nclass ADivideIt:\n    def solve(self):\n        for _ in range(int(input())):\n            n = int(input())\n            cnt = 0\n            while n != 1:\n                if n % 2 == 0:\n                    n //= 2\n                elif n % 3 == 0:\n                    n //= 3\n                    n *= 2\n                elif n % 5 == 0:\n                    n *= 4\n                    n //= 5\n                else:\n                    print(-1)\n                    break\n                cnt += 1\n            else:\n                print(cnt)\n\n\n\n\nsolver = ADivideIt()\ninput = sys.stdin.readline\n\nsolver.solve()\n", "passed": true, "time": 0.15, "memory": 14100.0, "status": "done"}, {"code": "def f(n):\n    s=0\n    while n%2==0:\n        n//=2\n        s+=1\n    while n%3==0:\n        n//=3\n        s+=2\n    while n%5==0:\n        n//=5\n        s+=3\n    if n!=1:\n        return -1\n    else:\n        return s\nfor k in range(int(input())):\n    print(f(int(input())))\n", "passed": true, "time": 0.14, "memory": 14356.0, "status": "done"}, {"code": "def ain():\n    return map(int,input().split())\ndef lin():\n    return list(ain())\n\n\ndef plist(l):\n    for x in l:\n        print(x, end= ' ')\n    print()\n\ndef indexof(l,v,l3):\n    return l3[v]\n\n\nfor _ in range(int(input())):\n    n = int(input())\n    c = 0\n    f=  0\n    while n != 1:\n        if n%2 == 0:\n            n =n //2\n        elif n%3 == 0:\n            n = (2*n)//3\n        elif n%5 == 0:\n            n = (4*n) //5\n        else:\n            f = 1\n            print(-1)\n            break\n        c+=1\n    if f == 0:\n        print(c)\n\n\n", "passed": true, "time": 0.97, "memory": 14216.0, "status": "done"}, {"code": "q = int(input())\nfor q in range(q):\n    n = int(input())\n    ans = 0\n    while (n != 1):\n        if n % 5 == 0:\n            n = n // 5 * 4\n        elif n % 3 == 0:\n            n = n // 3 * 2\n        elif n & 1 == 0:\n            n >>= 1\n        else:\n            break\n        ans += 1\n    if n != 1:\n        print(-1)\n    else:\n        print(ans)\n", "passed": true, "time": 0.14, "memory": 14140.0, "status": "done"}, {"code": "def calc(n):\n    re = 0\n    while n % 5 == 0:\n        n = n//5*4\n        re += 1\n    while n % 3 == 0:\n        n = n//3*2\n        re += 1\n    while n % 2 == 0:\n        n = n//2\n        re += 1\n    if n == 1:\n        return re\n    else:\n        return -1\n\nQ = int(input())\nfor _ in range(Q):\n    print(calc(int(input())))\n", "passed": true, "time": 0.14, "memory": 14280.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    ops = 0\n    while not n%2:\n        n = n//2\n        ops += 1\n    while not n%3:\n        n = n//3\n        ops += 2\n    while not n%5:\n        n = n//5\n        ops += 3\n    print(-1 if n>1 else ops)\n", "passed": true, "time": 0.14, "memory": 14272.0, "status": "done"}, {"code": "def solve(n):\n    p2, p3, p5 = 0, 0, 0\n    while n % 2 == 0:\n        n //= 2;\n        p2 += 1\n    while n % 3 == 0:\n        n //= 3\n        p3 += 1\n    while n % 5 == 0:\n        n //= 5\n        p5 += 1\n    if n != 1:\n        return -1\n    return 2 * p3 + 3 * p5 + p2\n\nq = int(input())\nfor i in range(q):\n    n = int(input())\n    print(solve(n))", "passed": true, "time": 0.14, "memory": 14296.0, "status": "done"}, {"code": "q = int(input())\nfor _ in range(q):\n    n = int(input())\n    ans = 0\n    while n % 5 == 0:\n        ans += 3\n        n //= 5\n    while n % 3 == 0:\n        ans += 2\n        n //= 3\n    while n % 2 == 0:\n        ans += 1\n        n //= 2\n    if n != 1:\n        print(-1)\n    else:\n        print(ans)\n\n    \n", "passed": true, "time": 0.14, "memory": 14128.0, "status": "done"}, {"code": "n = int(input())\nfor i in range(n):\n    q = int(input())\n    s = 0\n    while(q%5==0):\n        q = q//5\n        s+=3\n    while(q%3==0):\n        q = q//3\n        s+=2\n    while(q%2==0):\n        q = q//2\n        s+=1\n    if(q==1):\n        print(s)\n    else:\n        print(-1)\n", "passed": true, "time": 0.14, "memory": 14296.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    ans = 0\n    while n % 2 == 0:\n        n //= 2\n        ans += 1\n    while n % 3 == 0:\n        n //= 3\n        ans += 2\n    while n % 5 == 0:\n        n //= 5\n        ans += 3\n    if n == 1:\n        print(ans)\n    else:\n        print(-1)", "passed": true, "time": 0.14, "memory": 14332.0, "status": "done"}, {"code": "for i in range(int(input())):\n    n = int(input()) \n    cnt = 0\n    while n > 1:\n        cnt += 1\n        if n % 2 == 0:\n            n //= 2\n        elif n % 3 == 0:\n            n = 2 * n // 3\n        elif n % 5 == 0:\n            n = 4 * n // 5\n        else:\n            cnt = -1\n            break\n    print(cnt) \n            \n", "passed": true, "time": 0.14, "memory": 14340.0, "status": "done"}, {"code": "n = int(input())\nfor i in range(n):\n    x = int(input())\n    k = 0\n    while x != 1:\n        if x % 2 == 0:\n            x = x // 2\n            k += 1\n        elif x % 3 == 0:\n            x = x - x// 3\n            k += 1\n        elif x % 5 == 0:\n            x = x - x // 5\n            k+= 1\n        else:\n            k = -1\n            break\n    print(k)", "passed": true, "time": 0.14, "memory": 14076.0, "status": "done"}, {"code": "q = int(input())\n\nfor _ in range(q):\n    n = int(input())\n\n    moves = 0\n\n    while n % 5 == 0:\n        moves += 1\n        n = n // 5 * 4\n\n    while n % 3 == 0:\n        moves += 1\n        n = n // 3 * 2\n    while n % 2 == 0:\n        moves += 1\n        n //= 2\n\n    if n == 1:\n        print(moves)\n    else:\n        print(-1)\n", "passed": true, "time": 0.14, "memory": 14344.0, "status": "done"}, {"code": "q = int(input())\n\nfor t in range(q):\n    n = int(input())\n    ans = 0\n    while n%5 == 0:\n        n //= 5\n        ans += 3\n    while n%3 == 0:\n        n //= 3\n        ans += 2\n    while n%2 == 0:\n        n //= 2\n        ans += 1\n    if n == 1:\n        print(ans)\n    else:\n        print(-1)", "passed": true, "time": 0.14, "memory": 14224.0, "status": "done"}, {"code": "for i in range(int(input())):\n    x = int(input())\n    k = 0\n    fl = True\n    while fl:\n        fl = x % 2 == 0 or x % 3 == 0 or x % 5 == 0\n        if fl:\n            if x % 2 == 0:\n                while x % 2 == 0:\n                    x //= 2\n                    k += 1\n            elif x % 3 == 0:\n                x *= 2\n                x //= 3\n                k += 1\n            elif x % 5 == 0:\n                x *= 4\n                x //= 5\n                k += 1\n    if x != 1:\n        print(-1)\n    else:\n        print(k)\n                \n", "passed": true, "time": 0.14, "memory": 14124.0, "status": "done"}]