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 java.io.*;
import java.util.*;

public class solution {
    static class sort implements Comparator<ArrayList<Integer>> {

        @Override
        public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
            int c = o2.get(1).compareTo(o1.get(1));
            return c;
        }
    }

    public static void merge(long arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        long L[] = new long[n1];
        long R[] = new long[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void sort(long arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else return gcd(b, a % b);
    }

    public static long lcm(long a, long b) {
        long gcd = gcd(a, b);
        long pord = a * b;
        return pord / gcd;
    }

    static class graphs {
        private int V;
        private ArrayList<Integer> adj[];

        graphs(int v) {
            V = v;
            adj = new ArrayList[v];
            for (int i = 0; i < v; i++) {
                adj[i] = new ArrayList<>();
            }
        }

        void addedge(int u, int v) {
            adj[u].add(v);
        }

        void BFS(int v) {
            boolean visited[] = new boolean[V];
            Queue<Integer> Q = new LinkedList<>();
            visited[v] = true;
            Q.add(v);
            while (!Q.isEmpty()) {
                int temp = Q.peek();
                System.out.print(temp + " ");
                Q.remove();
                Iterator<Integer> it = adj[temp].listIterator();
                while (it.hasNext()) {
                    int n = it.next();
                    if (!visited[n]) {
                        visited[n] = true;
                        Q.add(n);
                    }
                }
            }
        }

        void DFSUtil(int v, boolean visited[]) {
            visited[v] = true;
            System.out.print(v + " ");
            Iterator<Integer> it = adj[v].listIterator();
            while (it.hasNext()) {
                int n = it.next();
                if (!visited[n]) {
                    DFSUtil(n, visited);
                }
            }
        }

        void DFS(int v) {
            boolean visited[] = new boolean[V];
            DFSUtil(v, visited);
        }
    }

    public static int Binaraysearch(long a[], int low, int high, long key) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == key) {
                return mid;
            } else if (a[mid] < key) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return -1;
    }

    public static void seive(boolean prime[]) {
        Arrays.fill(prime, true);
        int n = prime.length - 1;
        for (int p = 2; p * p <= n; p++) {
            if (prime[p] == true) {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
    }

    public static boolean random(long a, long b) {
        return a < b;
    }

    public static int subArraySum(int arr[], int n, int sum) {
        int curr_sum = arr[0], start = 0, i;
        for (i = 1; i <= n; i++) {
            // If curr_sum exceeds the sum, then remove the starting elements
            while (curr_sum > sum && start < i - 1) {
                curr_sum = curr_sum - arr[start];
                start++;
            }

            // If curr_sum becomes equal to sum, then return true
            if (curr_sum == sum) {
                int p = i - 1;
                if (p != start)
                    return 1;
            }

            // Add this element to curr_sum
            if (i < n)
                curr_sum = curr_sum + arr[i];

        }
        return 0;
    }

    static class pair {
        int x;
        int dis;

        public pair(int x, int dis) {
            this.x = x;
            this.dis = dis;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int ii = 0; ii < t; ii++) {
            Long n = Long.parseLong(br.readLine());
            int cnt2 = 0;
            int cnt3 = 0;
            while (n % 2 == 0) {
                n /= 2;
                ++cnt2;
            }
            while (n % 3 == 0) {
                n /= 3;
                ++cnt3;
            }
            if(n == 1 && cnt2<=cnt3){
                System.out.println(2*cnt3-cnt2);
            }
            else{
                System.out.println("-1");
            }
        }
    }
}