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

import math,collections 
  
# A function to print all prime factors of  
# a given number n 
def primeFactors(n): 
    f=[]
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        f.append(2) 
        n = n / 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,4,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            f.append(i) 
            n = n / i 
              
    # Condition if n is a prime 
    # number greater than 2 
    return f 
for _ in range(int(input())):
	n=int(input())
	if n==1:print(0)
	else:
		a=(primeFactors(n))
		d=collections.Counter(a)
		if 2 in d and 3 not in d:
			print(-1)
		elif 2 not in d and 3 in d:
			if 3**(d[3])!=n:
				print(-1)
			else:
				print(2*d[3])
		elif 2 in d and 3 in d:
			if d[2]>d[3]:
				print(-1)
			elif (2**(d[2]))*(3**(d[3]))!=n:
				print(-1)
			else:
				print(-d[2]+2*d[3]) 
		else:
			print(-1)
		# print(d)
		# #print(d)
		# k=sorted(list(d.keys()))
		# #print(k)
		# if len(k)==1:
		# 	if k!=[3]:
		# 		print(-1)
		# 	else: 
		# 		print(d[k[0]]*2)
		# elif len(k)==2:
		# 	if k!=[2,3]:
		# 		print(-1)
		# 	else: 
		# 		if d[2]>d[3]:
		# 			print(-1)
		# 		else:
		# 			cc=min(d[2],d[3])+(d[3]-d[2])*2
		# 			print(cc)

		# else:
		# 	print(-1)
		







