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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Vector;
import java.util.concurrent.ThreadLocalRandom;
public class CodeForces {
	
	 static class Range{
		
		String s;
		public Range(String s){
			this.s = s;
		}
		
		
		@Override
		public String toString() {
			return s;
		}
	}

	static class RangeComparator implements Comparator<Range>{

		public int compare(Range o1, Range o2) {
			String[] v1 = o1.s.split("#");
			String[] v2 = o2.s.split("#");
			int val1 = Integer.parseInt(v1[1])- Integer.parseInt(v1[0]);
			int val2 = Integer.parseInt(v2[1])- Integer.parseInt(v2[0]);
			if(val1>val2){
				return -1;
			}else if(val2>val1){
				return 1;
			}
			return o1.s.compareTo(o2.s);
		}
		
	}

	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static int[] getIntArray(BufferedReader br) throws IOException {
		String line = br.readLine();
		String[] values = line.split(" ");
		int[] arr = new int[values.length];
		for (int i = 0; i < values.length; i++) {
			arr[i] = Integer.parseInt(values[i]);
		}
		return arr;
	}
	
	public static long[] getLongArray(BufferedReader br) throws IOException {
		String line = br.readLine();
		String[] values = line.split(" ");
		long[] arr = new long[values.length];
		for (int i = 0; i < values.length; i++) {
			arr[i] = Long.parseLong(values[i]);
		}
		return arr;
	}
	
	public static Set<Integer> getFactors(int n){
		Set<Integer> set = new HashSet<>();
		for(int i=2;i<=Math.sqrt(n);i++){
			if(n%i==0){
				set.add(i);
				set.add(n/i);
			}
		}
		return set;
	}
	
	public static int[] decode(String s){
		String[] v = s.split("#");
		int[] arr = new int[2];
		arr[0] = Integer.parseInt(v[0]);
		arr[1] = Integer.parseInt(v[1]);
		return arr;
	}
	
	public static String encode(int a,int b){
		return a+"#"+b;
	}
	

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		
		
		
		
		String line = br.readLine();
		int t = Integer.parseInt(line);
		while (t-- > 0) {
			line = br.readLine();
			int n = Integer.parseInt(line);
			
			if(n==1){
				System.out.println("0");
			}
			else if(n%3!=0){
				System.out.println(-1);
			}else{
			int th=0;
			while(n%3==0){
				n=n/3;
				th++;
			}
			int tw=0;
			while(n%2==0){
				n=n/2;
				tw++;
			}
//			System.out.println(tw+" "+th);
			if(n!=1){
				System.out.println(-1);
			}else if(tw>th){
				System.out.println(-1);
			}else{
				int diff = th - tw;
				int ans = diff +th;
				
				System.out.println(ans);
				
			}
			}
			
			
		}
		
		
		
	}

}
 