1176_A. Divide it!
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 n/2 if n is divisible by 2; 
  2. Replace n with 2n/3 if n is divisible by 3; 
  3. Replace n with 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 ≤ q ≤ 1000) — the number of queries.

The next q lines contain the queries. For each query you are given the integer number n (1 ≤ n ≤ 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
```python
nq=int(input())
q=[int(input()) for i in range(nq)]
def check3(number):
    l=list(str(number))
    s=0
    for i in l:
       s+=int(i)
    if s%3==0 :
        return 'yes'
    else:
        return 'no'
def check5(number):
    if number%10==5 or number%10==0:
        return 'yes'
    else:
        return 'no'
def check2(number):
    if number%2==0:
        return 'yes'
    else:
        return 'no'
def check_div(number):
    temp=number
    counter=0
    if temp==1 or temp==0:
        print(0)
    elif temp==2:
        print(1)
    else:
        while True:
            if check5(temp)=='yes':
                counter+=1
                temp=(4*temp)//5
                if temp==5 or temp==3 or temp==2:
                    counter+=1
                    print(counter)
                    break
            elif check5(temp)=='no':
                if check3(temp)=='yes':
                    counter+=1
                    temp=(2*temp)//3
                    if temp==5 or temp==3 or temp==2:
                        counter+=1
                        print(counter)
                        break
                elif check3(temp)=='no':
                    if check2(temp)=='yes':
                        counter+=1
                        temp=temp//2
                        if temp==5 or temp==3 or temp==2:
                            counter+=1
                            print(counter)
                            break
                    elif check2(temp)=='no':
                        print(-1)
                        break
#main running function
for num in q:
    check_div(num)

```