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$.
[{"code": "for testcase in range(int(input())):\n    n = int(input())\n    cnt2, cnt3 = 0, 0\n    while n % 2 == 0:\n        n //= 2\n        cnt2 += 1\n    while n % 3 == 0:\n        n //= 3\n        cnt3 += 1\n\n    if n > 1 or cnt3 < cnt2:\n        print(-1)\n        continue\n\n    print(2 * cnt3 - cnt2)\n", "passed": true, "time": 0.16, "memory": 14260.0, "status": "done"}, {"code": "# for _ in range(1):\nfor _ in range(int(input())):\n    # n = map(int, input().split())\n    n = int(input())\n    # arr = list(map(int, input().split()))\n    # s = input()\n    x = 0\n    while n % 6 == 0:\n        x += 1\n        n //= 6\n    while n % 3 == 0:\n        x += 2\n        n //= 3\n    if n != 1:\n        x = -1\n    print(x)", "passed": true, "time": 0.16, "memory": 14060.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    x = n\n    twos = 0\n    threes = 0\n    while x % 2 == 0:\n        x //= 2\n        twos += 1\n    while x % 3 == 0:\n        x //= 3\n        threes += 1\n    if x == 1 and threes >= twos:\n        print(threes + threes - twos)\n    else:\n        print(-1)\n", "passed": true, "time": 0.5, "memory": 14112.0, "status": "done"}, {"code": "def read_int():\n    return int(input())\n\n\ndef read_ints():\n    return list(map(int, input().split(' ')))\n\n\nt = read_int()\nfor case_num in range(t):\n    n = read_int()\n    if n == 1:\n        print(0)\n    else:\n        two = 0\n        three = 0\n        while n % 2 == 0:\n            n //= 2\n            two += 1\n        while n % 3 == 0:\n            n //= 3\n            three += 1\n        if n != 1 or two > three:\n            print(-1)\n        else:\n            print(three * 2 - two)\n", "passed": true, "time": 0.15, "memory": 14232.0, "status": "done"}, {"code": "import sys\n\ninp = [int(x) for x in sys.stdin.read().split()]; ii = 0\n\nttt = inp[ii]; ii += 1\nfor _ in range(ttt):\n\tn = inp[ii]; ii += 1\n\te2, e3 = 0, 0\n\twhile n % 2 == 0:\n\t\tn /= 2\n\t\te2 += 1\n\twhile n % 3 == 0:\n\t\tn /= 3\n\t\te3 += 1\n\tif n > 1 or e2 > e3:\n\t\tprint(-1)\n\telse:\n\t\tprint(e3 - e2 + e3)", "passed": true, "time": 0.25, "memory": 14200.0, "status": "done"}, {"code": "import math\nimport collections\nimport sys\n\n\ndef inpu():\n    return input().split(' ')\n\n\ndef inti(a):\n    for i in range(len(a)):\n        a[i] = int(a[i])\n    return a\n\n\ndef inp():\n    a = inpu()\n    a = inti(a)\n    return a\n\n\nfor _ in range(int(input())):\n    n = int(input())\n    moves = 0\n    if n % 6 == 0:\n        while n % 6 == 0:\n            n = n//6\n            moves += 1\n    if n % 3 == 0:\n        while n % 3 == 0:\n            n = n//3\n            moves += 2\n    if n == 1:\n        print(moves)\n    else:\n        print(-1)\n", "passed": true, "time": 0.15, "memory": 14288.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    kek = dict()\n    kek[2] = 0\n    kek[3] = 0\n    i = 2\n    while i < 4 and n > 1:\n        if n % i == 0:\n            n //= i\n            kek[i] += 1\n        else:\n            i += 1\n    if n != 1:\n        print(-1)\n    else:\n        if kek[2] > kek[3]:\n            print(-1)\n        else:\n            ans = kek[3]\n            ans += kek[3] - kek[2]\n            print(ans)", "passed": true, "time": 0.16, "memory": 14108.0, "status": "done"}, {"code": "a=int(input())\nfor i in range(a):\n    n=int(input())\n    count=0\n    while(n%6==0):\n        n=n//6\n        count+=1\n    if(n==1):\n        print(count)\n        continue;\n    else:\n        while(n%3==0):\n            n=n//3\n            count+=2\n        if(n==1):\n            print(count)\n        else:\n            print(-1)\n", "passed": true, "time": 0.15, "memory": 14344.0, "status": "done"}, {"code": "import sys\n\nt = int(sys.stdin.readline().strip())\nfor _ in range(t):\n\tn = int(sys.stdin.readline().strip())\n\n\ttwo, three = 0, 0\n\twhile n%2 == 0:\n\t\tn //= 2\n\t\ttwo += 1\n\twhile n%3 == 0:\n\t\tn //= 3\n\t\tthree += 1\n\n\tif n > 1 or two > three:\n\t\tprint(-1)\n\t\tcontinue\n\n\telse:\n\t\tprint(three-two + three)\n", "passed": true, "time": 0.25, "memory": 14308.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tct2, ct3 = 0, 0\n\twhile n%2 == 0:\n\t\tn /= 2\n\t\tct2 += 1\n\twhile n%3 == 0:\n\t\tn /= 3\n\t\tct3 += 1\n\tif n > 1 or ct2 > ct3:\n\t\tprint(-1)\n\telse:\n\t\tprint(ct3 + ct3-ct2)\n", "passed": true, "time": 0.14, "memory": 14212.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n\nt=int(input())\nfor tests in range(t):\n    n=int(input())\n\n    TWO=0\n    THREE=0\n\n    while n%2==0:\n        TWO+=1\n        n//=2\n\n    while n%3==0:\n        THREE+=1\n        n//=3\n\n    if n!=1:\n        print(-1)\n    else:\n        if TWO>THREE:\n            print(-1)\n        else:\n            print(THREE-TWO+THREE)\n\n    \n", "passed": true, "time": 0.15, "memory": 14276.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    n = int(input())\n    div = [0,0]\n    while n%2 == 0:\n        n //= 2\n        div[0] += 1\n    while n%3 == 0:\n        n //= 3\n        div[1] += 1\n    if n != 1:\n        print(-1)\n        continue\n    print((div[1] - div[0]) + (div[1]) if div[1] >= div[0] else -1)", "passed": true, "time": 0.14, "memory": 14232.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    n, = map(int, input().split())\n    x = n\n    s = 0\n    while x != 1 and x%3 == 0:\n        if x%6 == 0:\n            x//=6\n            s+=1\n        else:\n            x*=2\n            s+=1\n    if x == 1:\n        print(s)\n    else:\n        print(-1)", "passed": true, "time": 0.15, "memory": 14076.0, "status": "done"}, {"code": "def deli(n):\n    n3 = 0\n    n2 = 0\n    while n % 3 == 0:\n        n //= 3\n        n3 += 1\n    while n % 2 == 0:\n        n //= 2\n        n2 += 1\n    if n != 1:\n        return -1, -1\n    else:\n        return n2,n3\ndef solve():\n    n = int(input())\n    a,b = deli(n)\n    if a == -1:\n        print(-1)\n    elif b < a:\n        print(-1)\n    else:\n        print(b + b - a)\n\nfor i in range(int(input())):\n    solve()", "passed": true, "time": 0.14, "memory": 14060.0, "status": "done"}, {"code": "\ntt = int(input())\n\nfor loop in range(tt):\n\n    n = int(input())\n\n    d2 = 0\n    d3 = 0\n\n    while n % 2 == 0:\n        d2 += 1\n        n //= 2\n\n    while n % 3 == 0:\n        d3 += 1\n        n //= 3\n\n    if n != 1 or d3 < d2:\n        print(-1)\n    else:\n        print(d3 + d3-d2)\n", "passed": true, "time": 0.14, "memory": 14176.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    n = int(input())\n    p2 = 0\n    p3 = 0\n    while n % 3 == 0:\n        n //= 3\n        p3 += 1\n    while n % 2 == 0:\n        n //= 2\n        p2 += 1\n    if n == 1:\n        diff = p3 - p2\n        if diff < 0:\n            print(-1)\n        else:\n            print(p3 + diff)\n    else:\n        print(-1)\n\n\n", "passed": true, "time": 0.15, "memory": 14300.0, "status": "done"}, {"code": "import sys\nimport math\nimport itertools\nimport functools\nimport collections\nimport operator\nimport fileinput\nimport copy\n\nORDA = 97  # a\ndef ii(): return int(input())\ndef mi(): return list(map(int, input().split()))\ndef li(): return [int(i) for i in input().split()]\ndef lcm(a, b): return abs(a * b) // math.gcd(a, b)\ndef revn(n): return str(n)[::-1]\ndef dd(): return collections.defaultdict(int)\ndef ddl(): return collections.defaultdict(list)\ndef sieve(n):\n    if n < 2: return list()\n    prime = [True for _ in range(n + 1)]\n    p = 3\n    while p * p <= n:\n        if prime[p]:\n            for i in range(p * 2, n + 1, p):\n                prime[i] = False\n        p += 2\n    r = [2]\n    for p in range(3, n + 1, 2):\n        if prime[p]:\n            r.append(p)\n    return r\ndef divs(n, start=1):\n    r = []\n    for i in range(start, int(math.sqrt(n) + 1)):\n        if (n % i == 0):\n            if (n / i == i):\n                r.append(i)\n            else:\n                r.extend([i, n // i])\n    return r\ndef divn(n, primes):\n    divs_number = 1\n    for i in primes:\n        if n == 1:\n            return divs_number\n        t = 1\n        while n % i == 0:\n            t += 1\n            n //= i\n        divs_number *= t\ndef prime(n):\n    if n == 2: return True\n    if n % 2 == 0 or n <= 1: return False\n    sqr = int(math.sqrt(n)) + 1\n    for d in range(3, sqr, 2):\n        if n % d == 0: return False\n    return True\ndef convn(number, base):\n    newnumber = 0\n    while number > 0:\n        newnumber += number % base\n        number //= base\n    return newnumber\ndef cdiv(n, k): return n // k + (n % k != 0)\ndef ispal(s):\n    for i in range(len(s) // 2 + 1):\n        if s[i] != s[-i - 1]:\n            return False\n    return True\n\n\nfor _ in range(ii()):\n    n = ii()\n\n    two, three = 0, 0\n    while n % 3 == 0:\n        n //= 3\n        three += 1\n    while n % 2 == 0:\n        n //= 2\n        two += 1\n    if n != 1 or two > three:\n        print(-1)\n    else:\n        print(three * 2 - two)\n\n", "passed": true, "time": 0.14, "memory": 14484.0, "status": "done"}, {"code": "# Created by: WeirdBugsButOkay\n# 28-06-2020, 20:08:49\n\nimport math\n\ndef solve() :\n    n = int(input())\n    p2, p3 = 0, 0\n    while n % 2 == 0 :\n        p2 += 1\n        n //= 2\n    while n % 3 == 0 :\n        p3 += 1\n        n //= 3\n    if p3 < p2 :\n        print(-1)\n    else :\n        if n != 1 :\n            print(-1)\n        else :\n            print((p3 - p2) + p3)\n\nt = 1\nt = int(input())\nfor _ in range (0, t) :\n    solve()\n", "passed": true, "time": 0.14, "memory": 14240.0, "status": "done"}, {"code": "for i in range(int(input())):\n\tn = int(input())\n\ttimes = 0\n\tcanDo = True\n\twhile (n != 1):\n\t\tif n%6 == 0:\n\t\t\tn = n//6\n\t\telif n%3 == 0:\n\t\t\tn *= 2\n\t\telse:\n\t\t\tcanDo = False\n\t\t\tbreak\n\t\ttimes += 1\n\tif canDo:\n\t\tprint(times)\n\telse:\n\t\tprint(\"-1\")\n", "passed": true, "time": 0.14, "memory": 14040.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    n = int(input())\n    count = 0\n    tmp = n\n    while(tmp % 2 == 0):\n        tmp //= 2\n        count += 1\n    count2 = 0\n    while(tmp % 3 == 0):\n        tmp //= 3\n        count2 += 1\n    if tmp != 1:\n        print(-1)\n\n    else:\n        if count > count2:\n            print(-1)\n        else:\n            ans = count2 - count\n            ans += count2\n            print(ans)\n", "passed": true, "time": 0.14, "memory": 14300.0, "status": "done"}, {"code": "def inp():\n    return(int(input()))\ndef inlt():\n    return(list(map(int,input().split())))\ndef insr():\n    s = input()\n    return(list(s[:len(s) ]))\ndef invr():\n    return(list(map(int,input().split())))\n\nn = inp()\n\nfor i in range(n):\n    n = inp()\n\n    if(n == 1):\n        print(0)\n    else:\n        t = 2\n        cnt = 0\n        while(n%2 == 0):\n            cnt += 1\n            n //= 2\n\n        t = 3\n        cnt2 = 0\n        while(n%3 == 0):\n            cnt2 += 1\n            n //= 3\n        if(cnt2 == 0 or n != 1 or cnt > cnt2):\n            print(-1)\n        else:\n            print(cnt2 - cnt + cnt2)\n", "passed": true, "time": 0.14, "memory": 14236.0, "status": "done"}, {"code": "t=int(input())\ndef fun(n):\n    ans=0\n    two=0\n    three=0\n    while n%2==0:\n        n/=2\n        two+=1\n    while n%3==0:\n        n/=3\n        three+=1\n    if n!=1:\n        print(-1)\n    else:\n        if two>three:\n            print(-1)\n        else:\n            print(2*three-two)\nwhile t:\n    t-=1\n    n=int(input())\n    fun(n)\n    \n", "passed": true, "time": 0.13, "memory": 14096.0, "status": "done"}]