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

#include <bits/stdc++.h>
int n, d = 0, s = 0, e, i1, t, i;
int po() {
  int a = n;
loop:
  if (a % 3 == 0) {
    a = a / 3;
    d++;
    goto loop;
  } else if (a == 1)
    return 0;
  else if (a % 2 != 0)
    return 1;
}
int op() {
  int a = n;
lo1op:
  if (a % 2 == 0) {
    a = a / 2;
    s++;
    goto lo1op;
  } else if (s > d)
    return 1;
  else
    return 0;
}
int main() {
  int i1, t, i;
  scanf("%d", &t);
  for (i1 = 1; i1 <= t; i1++) {
    scanf("%d", &n);
    if (n == 1) {
      printf("0\n");
      continue;
    }
    if (n % 3 != 0)
      printf("-1\n");
    else if (po())
      printf("-1\n");
    else if (op())
      printf("-1\n");
    else {
      int s1 = 0, d1 = 0;
      int a1 = n;
    loop:
      if (a1 % 3 == 0) {
        a1 = a1 / 3;
        d1++;
        goto loop;
      }
      a1 = n;
    lo1op:
      if (a1 % 2 == 0) {
        a1 = a1 / 2;
        s1++;
        goto lo1op;
      }
      e = 2 * d1 - s1;
      printf("%d\n", e);
    }
    d = 0;
    s = 0;
  }
  return 0;
}
