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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class testMemory {
	static Scanner sc =new Scanner(System.in);
	public static boolean check(int x,int y) {
		    if(y==(x+1)||y==(x-1))
		        return true;
		    else
		        return false;
	}
	
	public static void run() {
		int k=sc.nextInt();
		int key[]=new int[k];
		for(int i=0;i<k;i++)
			key[i]=sc.nextInt();
		//Arrays.sort(key);
		int l=sc.nextInt();
		int lock[]=new int[l];
		for(int i=0;i<l;i++)
			lock[i]=sc.nextInt();
		//Arrays.sort(lock);

	//	int j=0;
		for(int i=0;i<k;i++) {
           for(int j=0;j<l;j++) {
        	   if(check(key[i],lock[j]))
        		   System.out.println(key[i]);
        	   return;
           }
		}
	}
	
	public static void EhabTheXorcist() {
		long u=sc.nextLong();
		long v=sc.nextLong();
		if(v<u) {
			System.out.println(-1);
			return;
		}
		if(u==0&&v==0) {
			System.out.println(0);
			return;
		}
			
		if(u==v) {
			System.out.println(1);
			System.out.println(u);
			return;
		}
		if((u&1)!=0&&(v&1)==0) {
			System.out.println(-1);
			return;
		}
		if((u&1)==0&&(v&1)!=0) {
			System.out.println(-1);
			return;
		}
		long x=(v>>1)-(u>>1);
		if(u==0) {
			System.out.println(2);
			System.out.println(x+" "+x);
			return;
		}
		long l=u;
		long r=v;
		while(l < r) {
			//System.out.println(l+"    "+r);
			long m = (l>>1)+(r>>1);
			long t=m^u;
			long s=t+m;
			//System.out.println("m "+m+" t "+t);
			if(s==v) {
				System.out.println(2);
				System.out.println(m+" "+t);
				return;
			}
			else if(s>v) {
				r=m-1;
			}
			else {
				l=m+1;
			}
		}
		if(l==r) {
			if((l^r)==u&&l+r==v) {
				System.out.println(2);
				System.out.println(l+" "+r);
				return;
			}
		}
		System.out.println(3);
		System.out.println(u+" "+x+" "+x);
		
		
		
		
		
	}
	public static String input() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			return br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return null;
	}
	public static int inputInt() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int x=0;
		try {
			st = new StringTokenizer(br.readLine());
			 x= Integer.parseInt(st.nextToken());
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		return x;
	}
	public static void Hotelier() {
		 int n=Integer.parseInt(sc.nextLine());
		 StringBuilder s = new StringBuilder();
		 s.append(input());
		 //
		 int []mask=new int[10];
		 for(int i=0;i<s.length();i++) {
			 
			 if(s.charAt(i)=='R') {
				 //System.out.println("R");
				 for(int j=mask.length-1;j>=0;j--) {
					 if(mask[j]==0) {
						 mask[j]=1;
						 break;
					 }
				 }

			 }
			 //8
			 //LLRL1RL1
			 else if(s.charAt(i)=='L') {
				 //System.out.println("L");
				 for(int j=0;j<mask.length;j++) {
					 if(mask[j]==0) {
						 mask[j]=1;
						 break;
					 }
				 }
			 }
			 else {
				 System.out.println((char)s.charAt(i)+" "+i);
				 //mask[((char)s.charAt(i))-48]=0;
				
			 }
			 //System.out.println(Arrays.toString(mask));
			 
		 }
		 for(int i=0;i<10;i++) {
			 System.out.print(mask[i]);
		 }
		 System.out.println();
	}
	public static void  GameWithString() {
		String s=input();
		Stack <Character>s1=new Stack<Character>();
		Stack <Character>s2=new Stack<Character>();
		for(int i=0;i<s.length();i++) {
			s1.push(s.charAt(i));
		}
		boolean f=true;
		while(!s1.isEmpty()) {
			if(!s2.isEmpty()) {
				if(s1.peek()==s2.peek()) {
					s1.pop();
					s2.pop();
					f=!f;
					continue;
				}
			}
		//	else {
				s2.push(s1.pop());

			
		}
		if(f)
			System.out.println("NO");
		else
			System.out.println("YES");


	}
	public static void SerejaAndSuffixes() {
		int n=sc.nextInt();
		int m=sc.nextInt();

		int a[]=new int[n];
		int max=0;
		for(int i=0;i<a.length;i++) {
			a[i]=sc.nextInt();
			if(a[i]>max)max=a[i];
			//System.out.println("aaa");

		}
		boolean []mask=new boolean[max+1];
		int []temp=new int[n];
		temp[n-1]=1;
		mask[a[n-1]]=true;
		for(int i=n-2;i>=0;i--) {
			int x=temp[i+1];
			if(!mask[a[i]]) {
				mask[a[i]]=true;
				x++;
			}
			temp[i]=x;
		}
		for(int i=0;i<m;i++) {
			int y=sc.nextInt();
			System.out.println(temp[y-1]);
		}
		
		
	}
	public static void HitTheLottery() {
		int n=sc.nextInt();
		int count=0;
		int [] m= {100,20,10,5,1};
		for(int i=0;i<5;i++) {
			if(n>=m[i]) {
				int x=n/m[i];
				count+=x;
				n=n-x*m[i];
			}
		}
		System.out.println(count);

		
	}
	public static int lg(long x) {
		return (int)(Math.log10(x)/Math.log10(2));
	}
	public static void ANDORAndSquareSum() {
		int n=sc.nextInt();
		long m[]=new long[n];
		int a[]=new int[20];
		int maxb=0;
		for(int i=0;i<n;i++) {
			m[i]=sc.nextInt();
			long t=m[i];
			int bit=0;
			while(t>0) {
				if((t&1)!=0) {
					a[bit]++;
					if(a[bit]>maxb)
						maxb=a[bit];
				}
				bit++;
				t>>=1;
			}
		}
		long num[]=new long[maxb];
		for(int i=0;i<a.length;i++) {
			int j=0;
			while(a[i]>0) {
				num[j]=num[j]|(1<<i);
				j++;
				a[i]--;
			}
		}
		long sum=0;
		for(int i=0;i<num.length;i++) {
			sum+=(num[i]*num[i]);
		}
		System.out.println(sum);


		

		
	}
	public static void PolycarpTraining() {
		int n=sc.nextInt();
		//int a[]=new int[n];
		//TreeSet <Integer>t=new TreeSet<Integer>();
		LinkedList <Integer>l=new LinkedList<Integer>();
		for(int i=0;i<n;i++) {
			//a[i]=sc.nextInt();
			l.add(sc.nextInt());
		}
		
		Collections.sort(l);
		//System.out.println(l);
		//Arrays.sort(a);
		int days=1;
		for(int i=0;i<n;i++) {
			if(l.remove()>=days) {
				days++;
			}

		}
		System.out.println(days-1);
	}
	public static void PolycarpTraining2() {
		int n=sc.nextInt();
		int a[]=new int[n];
		//TreeSet <Integer>t=new TreeSet<Integer>();
		//LinkedList <Integer>l=new LinkedList<Integer>();
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
			//l.add(sc.nextInt());
		}
		
		//Collections.sort(l);
		//System.out.println(l);
		Arrays.sort(a);
		int days=1;
		for(int i=0;i<n;i++) {
			if(a[i]>=days) {
				days++;
			}

		}
		System.out.println(days-1);
	}
//	private static int daysAtindex(int currentDay,int currentContest) {
//		double t=(Math.sqrt(1+((currentDay+currentContest)*8))-1)/2;
//		return (int)t;
//	}
	
	public static void RequiredRemainder() {
		int t=sc.nextInt();
		for(int o=0;o<t;o++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			int n=sc.nextInt();
			int c1=(n-y)%x;// correct
			System.out.println(n-c1);
			int c=((n-y)/x)*x+y;
			System.out.println(c);
	
			
		}
	}
    static int binarySearch( int arr[],int x,int l,int r) 
    { 

        while (l <= r) { 
            int m = l + (r - l) / 2; 
            
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
    
    public static void MultiplyBy2DivideBy6() {
    	int t=sc.nextInt();
    	for(int i=0;i<t;i++) {
    		int n=sc.nextInt();
    		int c2=0;
    		int c3=0;
    		while(n%3==0) {
    			c3++;
    			n/=3;
    		}
    		while(n%2==0) {
    			c2++;
    			n>>=1;
    		}
    		if(n==1) {
    			if(c3>=c2) {
    				//c3-c2;
    				System.out.println(c3+(c3-c2));
    			}
    			else
    				System.out.println(-1);
    			
    		}
    		else
    			System.out.println(-1);
    	}
    }
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//run();
		//EhabTheXorcist();
//		long x1=699050&349525;
//		long x2=699050|349525;
//		long a=x1*x1;;
//		long b=x2*x2;
//		long s=1<<20;
//		long f=s|(~s);
//		System.out.println(b);
		//ANDORAndSquareSum();
		//Hotelier();
		 //GameWithString() ;
		//SerejaAndSuffixes();
		//HitTheLottery();
		//PolycarpTraining2();
		//System.out.println(daysAtindex(3,4));
		//RequiredRemainder();
		MultiplyBy2DivideBy6();

	}

}
