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>
using namespace std;
string yes[3] = {"YES", "Yes", "yes"};
string no[3] = {"NO", "No", "no"};
int countones(long long a) {
  int count = 0;
  while (a != 0) {
    count++;
    a = a & (a - 1);
  }
  return count;
}
unsigned int reverse_bits(register unsigned int x) {
  x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
  x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
  x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
  x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
  return ((x >> 16) | (x << 16));
}
long long Fib[] = {
    0,         1,         1,         2,          3,         5,
    8,         13,        21,        34,         55,        89,
    144,       233,       377,       610,        987,       1597,
    2584,      4181,      6765,      10946,      17711,     28657,
    46368,     75025,     121393,    196418,     317811,    514229,
    832040,    1346269,   2178309,   3524578,    5702887,   9227465,
    14930352,  24157817,  39088169,  63245986,   102334155, 165580141,
    267914296, 433494437, 701408733, 1134903170, 1836311903};
long long sum(long long n) { return (n * (n + 1)) / 2; }
long long rangesum(long long a, long long b) {
  if (a <= 1) return sum(b);
  return sum(b) - sum(a - 1);
}
bool isPowerOfTwo(int n) {
  if (n == 0) return false;
  return (ceil(log2(n)) == floor(log2(n)));
}
inline bool cmp(long long a, long long b) { return a > b; }
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
int t, n, ans;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> t;
  while (t--) {
    ans = 0;
    cin >> n;
    while (n > 1) {
      if (n % 6 == 0) {
        n /= 6;
        ++ans;
      } else {
        n *= 2;
        ++ans;
        if (n % 6 != 0) {
          ans = -1;
          break;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}
