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.*;
import java.math.*;
import java.lang.*;

import static java.lang.Math.*;

public class Main implements Runnable
{
  static class InputReader
  {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;
    private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public InputReader(InputStream stream)
    {
      this.stream = stream;
    }

    public int read()
    {
      if (numChars==-1)
        throw new InputMismatchException();

      if (curChar >= numChars)
      {
        curChar = 0;
        try
        {
          numChars = stream.read(buf);
        }
        catch (IOException e)
        {
          throw new InputMismatchException();
        }

        if(numChars <= 0)
          return -1;
      }
      return buf[curChar++];
    }

    public String nextLine()
    {
      String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
    }
    public int nextInt()
    {
      int c = read();

      while(isSpaceChar(c))
        c = read();

      int sgn = 1;

      if (c == '-')
      {
        sgn = -1;
        c = read();
      }

      int res = 0;
      do
      {
        if(c<'0'||c>'9')
          throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
      }
      while (!isSpaceChar(c));

      return res * sgn;
    }

    public long nextLong()
    {
      int c = read();
      while (isSpaceChar(c))
        c = read();
      int sgn = 1;
      if (c == '-')
      {
        sgn = -1;
        c = read();
      }
      long res = 0;

      do
      {
        if (c < '0' || c > '9')
          throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
      }
      while (!isSpaceChar(c));
        return res * sgn;
    }

    public double nextDouble()
    {
      int c = read();
      while (isSpaceChar(c))
        c = read();
      int sgn = 1;
      if (c == '-')
      {
        sgn = -1;
        c = read();
      }
      double res = 0;
      while (!isSpaceChar(c) && c != '.')
      {
        if (c == 'e' || c == 'E')
          return res * Math.pow(10, nextInt());
        if (c < '0' || c > '9')
          throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
      }
      if (c == '.')
      {
        c = read();
        double m = 1;
        while (!isSpaceChar(c))
        {
          if (c == 'e' || c == 'E')
            return res * Math.pow(10, nextInt());
          if (c < '0' || c > '9')
            throw new InputMismatchException();
          m /= 10;
          res += (c - '0') * m;
          c = read();
        }
      }
      return res * sgn;
    }

    public String readString()
    {
      int c = read();
      while (isSpaceChar(c))
        c = read();
      StringBuilder res = new StringBuilder();
      do
      {
        res.appendCodePoint(c);
        c = read();
      }
      while (!isSpaceChar(c));

      return res.toString();
    }

    public boolean isSpaceChar(int c)
    {
      if (filter != null)
        return filter.isSpaceChar(c);
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public String next()
    {
      return readString();
    }

    public interface SpaceCharFilter
    {
      public boolean isSpaceChar(int ch);
    }
  }

  public static void main(String args[]) throws Exception
  {
    new Thread(null, new Main(),"Main",1<<26).start();
  }
    //User-defined functions goes here...
  public void run()
  {
    InputReader sc= new InputReader(System.in);
    PrintWriter w= new PrintWriter(System.out);

    //Your code goes here...
    int t = sc.nextInt();
    int max = 1000001;
    boolean prime[] = new boolean[max];
    Arrays.fill(prime, true);
    ArrayList<Integer> primeNum = new ArrayList<>();
    prime[0] = false;
    prime[1] = false;
    for(int i=2; i*i<max; i++){
        if(prime[i] == true)
            {
                // Update all multiples of p
                primeNum.add(i);
                for(int p = i*i; p < max; p += i)
                    prime[p] = false;
            }
    }

    for(int q0=0; q0<t; q0++){
        int x = sc.nextInt();


        int done = 0;
        for(int i=0; i<primeNum.size(); i++){
            if(x%primeNum.get(i) == 0 && (primeNum.get(i)!=2 && primeNum.get(i)!=3)){
                w.println("-1");
                done=1;
                break;
            }
        }
        if(x==1){
            w.println("0");;
            done=1;
        }

        if(done==0){
            int twos = 0;
            int temp = x;
            while(temp%2==0){
                temp/=2;
                twos++;
            }

            int threes = 0;
            while(temp%3==0){
                temp/=3;
                threes++;
            }

            if(twos>threes){
                w.println("-1");
            }
            else if(temp==1){
                w.println((threes+(threes-twos)));
            }
            else
                w.println("-1");
        }

    }

    w.close();
  }
}
