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.util.*;
import java.io.*;
public class Solution{
  
    static class pair /*implements Comparable<pair>*/{
        long a,b;
        pair(long x,long y){
            a=x;b=y;
        }
        // public long compareTo(pair t){
        //   if(t.a==this.a)
        //   return this.b-t.b;
        //   return this.a-t.a;
		   
        // }
    }
    // public static ArrayList<pair> bfs(String[] a,int r,int c){
    //     ArrayList<pair> ans=new ArrayList<>();
    //     Queue<pair> q=new LinkedList<>();
    //     int[][] dxy={{-1,0,1,0},{0,-1,0,1}};
    //     q.add(new pair(r,c));
    //     HashSet<String> h=new HashSet<>();
    //     while(!q.isEmpty()){
    //         pair f=q.poll();
    //         ans.add(f);h.add(f.a+" "+f.b);
    //         for(int i=0;i<4;i++){
    //             int dx=f.a+dxy[0][i];
    //             int dy=f.b+dxy[1][i];
    //             if(dx<0||dy<0||dx>=a.length||dy>=a.length||h.contains(dx+" "+dy)||
    //             a[dx].charAt(dy)=='1')
    //             continue;
    //             q.add(new pair(dx,dy));
    //             h.add(dx+" "+dy);
    //         }
    //     }
    //     return ans;
    // }    

    /*
    1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4 
*/
    public static int pow(int a, int n) {
		long ans = 1;
		long base = a;
		while (n != 0) {
			if ((n & 1) == 1) {
				ans *= base;
				ans %= 1000000007;
			}
			base = (base * base) % 1000000007;
			n >>= 1;
		}
		return (int) ans % 1000000007;
	}
	public static int find(int x){
	    int i=1;int f=0;
	    while(x>0){
	        if((x&1)==0)f=i;
	        x>>=1;i++;
	    }
	    return f;
	}
	public static boolean good(int x){
	    
	    if((((x+1)&x))==0)
	    return true;
	    return false;
	}
	public static long f(long n){
	  
	   long val=2;
	   long preval=0;int i=1;
	   while(n>=val){
	       i++;
	       preval=val;
	       val=3*i+val-1;
	       
	   }
	   
	   return preval;
	   
	}
	public static boolean bfs(ArrayList<Integer>[] a,int n,int[] b){
	    Queue<Integer> p=new LinkedList<>();
	    boolean v[]=new boolean[n];
	    v[0]=true;int k=0;
	    if(b[0]!=0)return false;
	    p.add(0);int c=1;
	    HashSet<Integer> h=new HashSet<Integer>();
	    h.add(0);
	    while(!p.isEmpty()){
	        int f=p.poll();k++;
	        if(h.contains(f))h.remove(f);
	        else return false;
	        v[f]=true;
	        c--;
	
	       for(int i:a[f]){
	           if(!v[i]){
	           p.add(i);v[i]=true;}
	       }
	          if(c==0){
	              c=p.size();
	       if(h.size()!=0)return false;
	       for(int j=k;j<k+p.size();j++)
	       h.add(b[j]);
	   }
	    }
	    return true;
	    
	}
	public static int mi(int[] a,int k,int[] dp,int n){
	    int max=0;
	    for(int i=1;i*i<=k;i++){
	      //  System.out.println("fact "+i);
	        if(k%i==0&&(a[i-1]<a[k-1])){
	            
	      //  System.out.println(i+" "+dp[i-1]+" "+a[i-1]+" ");
	        max=Math.max(dp[i-1],max);}
	        if(k%i==0&&(a[k/i-1]<a[k-1])){
	            
	      //  System.out.println(i+" "+dp[i-1]+" "+a[i-1]+" ");
	        max=Math.max(dp[k/i-1],max);}
	        
	    }
	    return max;
	}
	    public static void dfs(ArrayList<Integer> a[],boolean[] v,int n,int llllll){
     v[n]=true;
     llllll=Math.max(n,llllll);
  //   System.out.println(max);
        for(int i=0;i<a[n].size();i++){
            if(!v[a[n].get(i)]){
         dfs(a,v,a[n].get(i),llllll);
            }
           
        }
       
        
    }
    public static int bfs(ArrayList<Integer>[] a,int n,int x){
        boolean[] v=new boolean[n];
        int ans=0;
        Queue<Integer> q=new LinkedList<>();
        q.add(x);
     
        
        	
        while(!q.isEmpty()){
            int f=q.poll();
            v[f]=true;
            if(a[f].size()-1==0||a[f].size()==0)continue;
          ans+=a[f].size()-1;
            for(int i:a[f]){
                if(!v[i]){
                    q.add(i);v[i]=true;
                }
            }
        }
        return ans;
    }
    public static int gcd(int a,int b){
        if(a==0)return b;
        return gcd(b%a,a);
    }
    public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
 
 			int t =s.nextInt();
  	StringBuilder st=new StringBuilder();
 	
 	
 		while(t-- > 0) {
            long n=s.nextLong();
            long ans=-1;
if(n==1)
ans=0;
else{
    long c=0;
    while(n>0&&n%3==0){
        n/=3;c++;
    }
    if(c!=0&&(n==1||(n>1&&n%2==0))){
        long c2=0;
        while(n>0&&n%2==0){
            c2++;n/=2;
        }
        if(c>=c2&&n==1)
        ans=c+(c-c2);
    }
}
  

st.append(ans+"\n");
 		    
 		}
  System.out.println(st);
  
   
/*
12339
0
15
54306
999999995
185
999999998

2
1
3
1
6


6 23 21
1 1000 0
2 1 2

0
40
41664916690999888

1 
1 2 
2 1 3 
3 1 2 4 
2 4 1 3 5 
3 4 1 5 2 6 

1 11
5 35
3 6
0 42
0 0
1 2
3 4




6 45 46
2 2 1
3 4 2
4 4 3
*/


  
	
        
    }
}

