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;
long long int power(long long int x, long long int y);
long long int mpower(long long int x, long long int y, long long int p);
long long int modInv(long long int a, long long int m);
long long int gcdExtended(long long int a, long long int b, long long int *x,
                          long long int *y);
bool isPrime(long long int n);
long long int lvl[1000][1000];
bool A[1000][1000];
long long int modInv(long long int a, long long int m) {
  long long int x, y;
  long long int g = gcdExtended(a, m, &x, &y);
  long long int res = (x % m + m) % m;
  return res;
}
long long int gcdExtended(long long int a, long long int b, long long int *x,
                          long long int *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
long long int gcd(long long int x, long long int y) {
  return (x == 0) ? y : gcd(y % x, x);
}
long long int mpower(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
bool sortbysec(const pair<long long int, long long int> &a,
               const pair<long long int, long long int> &b) {
  return (a.second < b.second);
}
void addEdge(vector<long long int> adj[], long long int u, long long int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}
void DFSE(vector<long long int> adj[], vector<bool> &visited, long long int u) {
  long long int i;
  visited[u] = true;
  cout << u << " ";
  for (long long int i = 0; i < adj[u].size(); i++) {
    if (visited[adj[u][i]] == false) {
      DFSE(adj, visited, adj[u][i]);
    }
  }
}
void DFS(vector<long long int> adj[], long long int u, long long int v) {
  long long int i;
  vector<bool> visited(v, false);
  for (long long int i = 0; i < v; i++) {
    if (visited[i] == false) {
      DFSE(adj, visited, i);
    }
  }
}
long long int power(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y = y >> 1;
    x = x * x;
  }
  return res;
}
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  long long int p = sqrt(n);
  for (int i = 5; i <= p; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long int pow(long long int base, long long int expo, long long int m) {
  if (m == 1) return 0;
  long long int ans = 1, y = base % m;
  while (expo > 0) {
    if (expo & 1) ans = ((ans)*y) % m;
    y = (y * y) % m;
    if (y < 0) y += m;
    expo = expo >> 1;
  }
  if (ans < 0) {
    ans = (m - abs(ans) % m);
    return ans;
  }
  return ans % m;
}
vector<long long int> Divisors(long long int n) {
  vector<long long int> vec;
  vec.clear();
  for (long long int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i)
        vec.push_back(i);
      else {
        vec.push_back(i);
        vec.push_back(n / i);
      }
    }
  }
  return vec;
}
long long int two(long long int n) {
  long long int c = 0;
  while (n % 2 == 0) {
    c++;
    n /= 2;
  }
  return c;
}
long long int three(long long int n) {
  long long int c = 0;
  while (n % 3 == 0) {
    c++;
    n /= 3;
  }
  return c;
}
void slv() {
  long long int t, n, m, q, p, r, c, d, x, y, k, z, h, o, e, l, u, i, j, a, b;
  string s, s1, s2;
  cin >> n;
  b = two(n);
  c = three(n);
  if (n == 1)
    cout << 0 << '\n';
  else if (c == 0 && n != 1)
    cout << -1 << '\n';
  else if (b > c)
    cout << -1 << '\n';
  else if (pow(2, b) * pow(3, c) != n)
    cout << -1 << '\n';
  else
    cout << b + 2 * (c - b) << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int t, n, m, k, q, p, r, a, b, c, d, x, y, z, h, o, e, l, u, i, j;
  t = 1;
  cin >> t;
  while (t--) {
    slv();
  }
}
