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

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{   
	public static void main (String[] args) throws java.lang.Exception
	{  FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int t=in.nextInt();
	    while(t>0){
	        --t;
	        int x=in.nextInt();
	        if(x==1)
	        System.out.println(0);
	        else{
	            int two=0;
	            while(x%2==0){
	                x/=2;
	                ++two;
	            }
	            int three=0;
	            while(x%3==0){
	                x/=3;
	                ++three;
	            }
	            if(x!=1)
	            System.out.println(-1);
	            else{
	                if(two>three)
	                System.out.println(-1);
	                else{
	                    System.out.println(three+(three-two));
	                }
	            }
	        }
	    }
	}
}
	/* This is for sorting first according to gain[1] if gain[1] is same the gain[0]
Arrays.sort(gain, (long[] l1, long[] l2) -> {
	        if(l1[1] != l2[1])return Long.compare(l2[1], l1[1]);//Sorting in non-increasing order of gain
	        return Long.compare(l1[0], l2[0]);//Choosing smallest bit among all bits having same gain
	    });
*/
class pair{
    int x,y;
    pair(int x,int y){
        this.x=x;
        this.y=y;
    }
}	
class CompareValue { 
  
    static void compare(pair arr[], int n) 
    { 
        Arrays.sort(arr, new Comparator<pair>() { 
        public int compare(pair p1, pair p2) 
            { 
                return p1.y - p2.y; 
            } 
        }); 
    } 
}
class CompareKey{
    static void compare(pair arr[],int n){
        Arrays.sort(arr,new Comparator<pair>(){
            public int compare(pair p1,pair p2)
            {
                return p2.x-p1.x;
            }
        });
    }
}
class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}	