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

# 	m=(l+# 	c.append([l-r,m])
# 	# c[m]=(r-l,l)
# 	fun(l,m-1)
# 	fun(m+1,r)
def perform_bubble_sort(blist):
	cmpcount, swapcount = 0, 0
	blist=list(map(int,input().split()))
	for j in range(len(blist)):
	        for i in range(1, len(blist)-j):
	                cmpcount += 1
	                if blist[i-1] > blist[i]:
	                	swapcount += 1
	                	blist[i-1], blist[i] = blist[i], blist[i-1]
	print(swapcount)
def fun(l,c,d):
	if(c==n):
		return d
	if(c%2==0):
		d=max(fun(l[:-1],c+1,d+l[-1]),fun(l[1:],c+1,d+l[0]))
	else:
		d=min(fun(l[1:],c+1,d-l[0]),fun(l[:-1],c+1,d-l[-1]))
	return d
t=int(input())
# t=1
while t:#a = [list(map(int, input().split())) for i in range(n)]	
	t-=1
	n=int(input())
	a=0;b=0
	while(n%2==0):
		n//=2
		a+=1
	while(n%3==0):
		n//=3
		b+=1
	if(n>1):
		print(-1)
	elif(a>b):
		print(-1)
	else:
		print((b-a)+b)
	# l=list(map(int,input().split()))
	# a=[0 for i in range(n+1)]
	# x,y,n=map(int,input().split())
	# if(n%x==y):
	# 	print(n)
	# else:
	# 	k=(n%x)
	# 	a=0
	# 	if(k<y):
	# 		a=(n-x+abs(k-y))
	# 	else:
	# 		a=(n-abs(k-y))
	# 	print(a)
		# print(((n-y)//x)*x)

	# print(((n//x)+y)*x)






	# N, S = map(int,input().split())
	# A = list(map(int,input().split()))
	# mod = 998244353
	# dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
	# dp[0][0] = 1
	# for i in range(N) : 
	#     for j in range(S + 1) : 
	#         dp[i + 1][j] += 2 * dp[i][j]
	#         dp[i + 1][j] %= mod 
	#         if j + A[i] <= S : 
	#             dp[i + 1][j + A[i]] += dp[i][j]
	#             dp[i + 1][j + A[i]] %= mod
	# print(dp[N][S])




# stdout.flush()
# https://codeforces.com/contest/1320/problem/A
# https://codeforces.com/contest/431/problem/B
# a_dictionary = {"a": 1, "b": 2, "c": 3}
# max_key = max(a_dictionary, key=a_dictionary.get)
# a_dictionary = {"a": 1, "b": 2, "c": 3}
# all_values = a_dictionary.values()
# max_value = max(all_values)
# ans1=sorted(d.items(), key=lambda x:x[1], reverse=True)[0][1]
