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 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow. 

The only line of the test case contains one integer $n$ ($1 \le n \le 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$:

  Divide by $6$ and get $2519424$;  divide by $6$ and get $419904$;  divide by $6$ and get $69984$;  divide by $6$ and get $11664$;  multiply by $2$ and get $23328$;  divide by $6$ and get $3888$;  divide by $6$ and get $648$;  divide by $6$ and get $108$;  multiply by $2$ and get $216$;  divide by $6$ and get $36$;  divide by $6$ and get $6$;  divide by $6$ and get $1$.

Difficulty: introductory

Starter code:

Solutions:
for testcase in range(int(input())):
    n = int(input())
    cnt2, cnt3 = 0, 0
    while n % 2 == 0:
        n //= 2
        cnt2 += 1
    while n % 3 == 0:
        n //= 3
        cnt3 += 1

    if n > 1 or cnt3 < cnt2:
        print(-1)
        continue

    print(2 * cnt3 - cnt2)


# for _ in range(1):
for _ in range(int(input())):
    # n = map(int, input().split())
    n = int(input())
    # arr = list(map(int, input().split()))
    # s = input()
    x = 0
    while n % 6 == 0:
        x += 1
        n //= 6
    while n % 3 == 0:
        x += 2
        n //= 3
    if n != 1:
        x = -1
    print(x)

for _ in range(int(input())):
    n = int(input())
    x = n
    twos = 0
    threes = 0
    while x % 2 == 0:
        x //= 2
        twos += 1
    while x % 3 == 0:
        x //= 3
        threes += 1
    if x == 1 and threes >= twos:
        print(threes + threes - twos)
    else:
        print(-1)


def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


t = read_int()
for case_num in range(t):
    n = read_int()
    if n == 1:
        print(0)
    else:
        two = 0
        three = 0
        while n % 2 == 0:
            n //= 2
            two += 1
        while n % 3 == 0:
            n //= 3
            three += 1
        if n != 1 or two > three:
            print(-1)
        else:
            print(three * 2 - two)


import sys
import random
from math import *
 
def input():
    return sys.stdin.readline().strip()
 
def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def linput():
    return list(input())
 
def rinput():
    return map(int, tinput())

def fiinput():
    return map(float, tinput())
 
def rlinput():
    return list(map(int, input().split()))
def trinput():
    return tuple(rinput())

def srlinput():
    return sorted(list(map(int, input().split())))

def NOYES(fl):
    if fl:
        print("NO")
    else:
        print("YES")
def YESNO(fl):
    if fl:
        print("YES")
    else:
        print("NO")
    
def main():  
    n = iinput()
    #k = iinput() 
    #m = iinput() 
    #n = int(sys.stdin.readline().strip()) 
    #n, k = rinput()
    #n, m = rinput()
    #m, k = rinput()
    #n, k, m = rinput()
    #n, m, k = rinput()
    #k, n, m = rinput()
    #k, m, n = rinput() 
    #m, k, n = rinput()
    #m, n, k = rinput()
    #q = srlinput()
    #q = linput()
    t, g = 0, 0
    while n % 3 == 0:
        g += 1
        n //= 3
    while n % 2 == 0:
        n //= 2
        t += 1
    if n != 1 or t > g:
        print(-1)
    else:
        print(g * 2 - t)
    

    
for inytd in range(iinput()):
    main()

import sys

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0

ttt = inp[ii]; ii += 1
for _ in range(ttt):
	n = inp[ii]; ii += 1
	e2, e3 = 0, 0
	while n % 2 == 0:
		n /= 2
		e2 += 1
	while n % 3 == 0:
		n /= 3
		e3 += 1
	if n > 1 or e2 > e3:
		print(-1)
	else:
		print(e3 - e2 + e3)

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

for _ in range(val()):
    n = val()
    ans = 0
    if n == 1:
        print(ans)
        continue
    while n != 1:
        ans += 1
        if n%6 == 0:
            n//=6
        else:n *= 2
        if ans > 100:
            ans = -1
            break
    print(ans)

import math
import collections
import sys


def inpu():
    return input().split(' ')


def inti(a):
    for i in range(len(a)):
        a[i] = int(a[i])
    return a


def inp():
    a = inpu()
    a = inti(a)
    return a


for _ in range(int(input())):
    n = int(input())
    moves = 0
    if n % 6 == 0:
        while n % 6 == 0:
            n = n//6
            moves += 1
    if n % 3 == 0:
        while n % 3 == 0:
            n = n//3
            moves += 2
    if n == 1:
        print(moves)
    else:
        print(-1)


for _ in range(int(input())):
    n = int(input())
    kek = dict()
    kek[2] = 0
    kek[3] = 0
    i = 2
    while i < 4 and n > 1:
        if n % i == 0:
            n //= i
            kek[i] += 1
        else:
            i += 1
    if n != 1:
        print(-1)
    else:
        if kek[2] > kek[3]:
            print(-1)
        else:
            ans = kek[3]
            ans += kek[3] - kek[2]
            print(ans)

a=int(input())
for i in range(a):
    n=int(input())
    count=0
    while(n%6==0):
        n=n//6
        count+=1
    if(n==1):
        print(count)
        continue;
    else:
        while(n%3==0):
            n=n//3
            count+=2
        if(n==1):
            print(count)
        else:
            print(-1)


import sys

t = int(sys.stdin.readline().strip())
for _ in range(t):
	n = int(sys.stdin.readline().strip())

	two, three = 0, 0
	while n%2 == 0:
		n //= 2
		two += 1
	while n%3 == 0:
		n //= 3
		three += 1

	if n > 1 or two > three:
		print(-1)
		continue

	else:
		print(three-two + three)


t = int(input())
for _ in range(t):
	n = int(input())
	ct2, ct3 = 0, 0
	while n%2 == 0:
		n /= 2
		ct2 += 1
	while n%3 == 0:
		n /= 3
		ct3 += 1
	if n > 1 or ct2 > ct3:
		print(-1)
	else:
		print(ct3 + ct3-ct2)


import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n=int(input())

    TWO=0
    THREE=0

    while n%2==0:
        TWO+=1
        n//=2

    while n%3==0:
        THREE+=1
        n//=3

    if n!=1:
        print(-1)
    else:
        if TWO>THREE:
            print(-1)
        else:
            print(THREE-TWO+THREE)

    


t = int(input())
for _ in range(t):
    n = int(input())
    div = [0,0]
    while n%2 == 0:
        n //= 2
        div[0] += 1
    while n%3 == 0:
        n //= 3
        div[1] += 1
    if n != 1:
        print(-1)
        continue
    print((div[1] - div[0]) + (div[1]) if div[1] >= div[0] else -1)

t = int(input())
for _ in range(t):
    n, = map(int, input().split())
    x = n
    s = 0
    while x != 1 and x%3 == 0:
        if x%6 == 0:
            x//=6
            s+=1
        else:
            x*=2
            s+=1
    if x == 1:
        print(s)
    else:
        print(-1)

def deli(n):
    n3 = 0
    n2 = 0
    while n % 3 == 0:
        n //= 3
        n3 += 1
    while n % 2 == 0:
        n //= 2
        n2 += 1
    if n != 1:
        return -1, -1
    else:
        return n2,n3
def solve():
    n = int(input())
    a,b = deli(n)
    if a == -1:
        print(-1)
    elif b < a:
        print(-1)
    else:
        print(b + b - a)

for i in range(int(input())):
    solve()


tt = int(input())

for loop in range(tt):

    n = int(input())

    d2 = 0
    d3 = 0

    while n % 2 == 0:
        d2 += 1
        n //= 2

    while n % 3 == 0:
        d3 += 1
        n //= 3

    if n != 1 or d3 < d2:
        print(-1)
    else:
        print(d3 + d3-d2)


t = int(input())
for _ in range(t):
    n = int(input())
    p2 = 0
    p3 = 0
    while n % 3 == 0:
        n //= 3
        p3 += 1
    while n % 2 == 0:
        n //= 2
        p2 += 1
    if n == 1:
        diff = p3 - p2
        if diff < 0:
            print(-1)
        else:
            print(p3 + diff)
    else:
        print(-1)




import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy

ORDA = 97  # a
def ii(): return int(input())
def mi(): return list(map(int, input().split()))
def li(): return [int(i) for i in input().split()]
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def revn(n): return str(n)[::-1]
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)
def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r
def divs(n, start=1):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
def prime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True
def convn(number, base):
    newnumber = 0
    while number > 0:
        newnumber += number % base
        number //= base
    return newnumber
def cdiv(n, k): return n // k + (n % k != 0)
def ispal(s):
    for i in range(len(s) // 2 + 1):
        if s[i] != s[-i - 1]:
            return False
    return True


for _ in range(ii()):
    n = ii()

    two, three = 0, 0
    while n % 3 == 0:
        n //= 3
        three += 1
    while n % 2 == 0:
        n //= 2
        two += 1
    if n != 1 or two > three:
        print(-1)
    else:
        print(three * 2 - two)



# Created by: WeirdBugsButOkay
# 28-06-2020, 20:08:49

import math

def solve() :
    n = int(input())
    p2, p3 = 0, 0
    while n % 2 == 0 :
        p2 += 1
        n //= 2
    while n % 3 == 0 :
        p3 += 1
        n //= 3
    if p3 < p2 :
        print(-1)
    else :
        if n != 1 :
            print(-1)
        else :
            print((p3 - p2) + p3)

t = 1
t = int(input())
for _ in range (0, t) :
    solve()


for i in range(int(input())):
	n = int(input())
	times = 0
	canDo = True
	while (n != 1):
		if n%6 == 0:
			n = n//6
		elif n%3 == 0:
			n *= 2
		else:
			canDo = False
			break
		times += 1
	if canDo:
		print(times)
	else:
		print("-1")


t = int(input())
for _ in range(t):
    n = int(input())
    count = 0
    tmp = n
    while(tmp % 2 == 0):
        tmp //= 2
        count += 1
    count2 = 0
    while(tmp % 3 == 0):
        tmp //= 3
        count2 += 1
    if tmp != 1:
        print(-1)

    else:
        if count > count2:
            print(-1)
        else:
            ans = count2 - count
            ans += count2
            print(ans)


def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) ]))
def invr():
    return(list(map(int,input().split())))

n = inp()

for i in range(n):
    n = inp()

    if(n == 1):
        print(0)
    else:
        t = 2
        cnt = 0
        while(n%2 == 0):
            cnt += 1
            n //= 2

        t = 3
        cnt2 = 0
        while(n%3 == 0):
            cnt2 += 1
            n //= 3
        if(cnt2 == 0 or n != 1 or cnt > cnt2):
            print(-1)
        else:
            print(cnt2 - cnt + cnt2)


t=int(input())
def fun(n):
    ans=0
    two=0
    three=0
    while n%2==0:
        n/=2
        two+=1
    while n%3==0:
        n/=3
        three+=1
    if n!=1:
        print(-1)
    else:
        if two>three:
            print(-1)
        else:
            print(2*three-two)
while t:
    t-=1
    n=int(input())
    fun(n)