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.InputStream;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class MulTDS {
  // static boolean[] primes;
  public static void main(String[] args) throws IOException {
    InputReader in = new InputReader(System.in);
    PrintWriter pw = new PrintWriter(System.out);
    int t, n, cntr;
    // getPrimes();
    t = in.nextInt();
    while(t-- > 0) {
      n = in.nextInt();
      cntr = 0;
      while(n % 6 == 0) {
        n /= 6;
        cntr++;
      }
      while(n % 3 == 0) {
        n /= 3;
        cntr+=2;
      }
      if (n == 1) pw.println(cntr);
      else pw.println(-1);
    }
    pw.close();
  }

  // static void getPrimes() {
  //   primes = new boolean[(int)1e6+1];
  //   Arrays.fill(primes, true);
  //   primes[0] = primes[1] = false;
  //   for (int i = 2; i*i < primes.length; i++) {
  //     if (primes[i]) {
  //       for (int j = i*i; j < primes.length; j+=i) {
  //         primes[j] = false;
  //       }
  //     }
  //   }
  // }

  // static ArrayList<Integer> pf(int a) {
  //   ArrayList<Integer> tmp = new ArrayList<>();
  //   int cntr = 0;
  //   while(a != 0) {

  //   }
  // }

  static class InputReader {
    BufferedReader br;
    StringTokenizer st;
    public InputReader(InputStream inputStream) {
      br = new BufferedReader(new InputStreamReader(inputStream));
      st = null;
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }
}