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

public class Multiply
{
	static Scanner sc=new Scanner(System.in);
	 static PrintWriter out=new PrintWriter(System.out);
	 
	 static void pn(Object o)
	 {
	 out.println(o);
	 out.flush();

	 }
	 static void p(Object o)
	 {
	 out.print(o);
	 out.flush();
	 }
	 static void pni(Object o)
	 {
	 out.println(o);System.out.flush();
	 }

	 static int I() throws IOException
	 { 
	 return sc.nextInt();
	 }
	 static long L()throws IOException
	 {
	 return sc.nextLong();
	 }
	 static double D()throws IOException
	 {
	 return sc.nextDouble();
	 }
	 static String S()throws IOException
	    {
	        return sc.next();
	     }
	 static char C() throws IOException
	 {
	     return sc.next().charAt(0);
	 }	

	   static int[] Ai (int n) throws IOException {
			int[] arr = new int[n];
		
			
			for(int i = 0; i < n; i++) arr[i] = I();
			
			return arr;
		}
	  static String[] As(int n) throws IOException {
			String s[] = new String[n];
			
			
			
			for(int i = 0; i < n; i++) s[i] = S();
			
			return s;
		}
	   static long[] Al (int n) throws IOException {
			long[] arr = new long[n];
		
			
			for(int i = 0; i < n; i++) arr[i] = L();
			
			return arr;
		}
		static void process() throws IOException
	{
			long n=L();int c=0;
			boolean flag=false;
			if(n==1)
			{
				pn(0);
			}
			else
			{
				while(n!=1 && n>0)
				{
					if(n%6==0)
					{
						n=n/6;c++;
					}
					else
				    if(n%3==0)
				    {
				    	n=n*2;c++;
				    }
				    else
				    {
				    	flag=true;
				    	break;
				    }
				}
            if(flag==true)
            {
            	pn(-1);
            }
            else
            {
            	pn(c);
            }
            }
	}
	
	

			public static void main(String[] ars)throws IOException
			{
				int t=I();
				while(t-->0)
				process();
			}
			
			}
		        
			