You are given an integer n. In one move, you can either multiply n by two or divide n by 6 (if it is divisible by 6 without the remainder).

Your task is to find the minimum number of moves needed to obtain 1 from n or determine if it's impossible to do that.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow. 

The only line of the test case contains one integer n (1 ≤ n ≤ 10^9).

Output

For each test case, print the answer — the minimum number of moves needed to obtain 1 from n if it's possible to do that or -1 if it's impossible to obtain 1 from n.

Example

Input


7
1
2
3
12
12345
15116544
387420489


Output


0
-1
2
-1
-1
12
36

Note

Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer 15116544:

  1. Divide by 6 and get 2519424; 
  2. divide by 6 and get 419904; 
  3. divide by 6 and get 69984; 
  4. divide by 6 and get 11664; 
  5. multiply by 2 and get 23328; 
  6. divide by 6 and get 3888; 
  7. divide by 6 and get 648; 
  8. divide by 6 and get 108; 
  9. multiply by 2 and get 216; 
  10. divide by 6 and get 36; 
  11. divide by 6 and get 6; 
  12. divide by 6 and get 1. 
1
999838675

-1

# in order for a number to be able to become 1 from multiplying by 2 or divding by 6 
# the numbers must be able if we miltiply by 2 sum amount of time to be devisable by 6
# in order for a number to be devisable by 6 it needes to be devisable by its compositoin 2,3
# since we can multiply my two we assume we hve infinit amount of 2
# but we have 3 only the amount in the number it self
# we can understand that for a number to get to 1 eventually it needs to have more 3 than 2  and not be a composit of other prime

# count how many times number is devisable by 3
# count how many times number is devisable by 2
# make sure the remaning number is 1 and count3 >= count 2
# and return count2 + 2*(count3 - count2)
# 2*(count3 - count2) is for every time there is a need to multiply by 2 and devide by 6

def FindCount(n):
    count3 =0
    while n%3==0:
        count3+=1
        n//=3
    
    count2 =0
    while n%2==0:
        count2+=1
        n//=2
    if n!=1 or count2>count3:
        return -1
    return count2+2*(count3-count2)
FindCount(3)
for _ in range(int(input())):
    print(FindCount(int(input())))