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>
//pbds
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>   using orderedSet =tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
#define endl '\n'
//BFS+DFS
#define boundary(i,j) (i>=0 && i<n && j>=0 && j<m)
int X[]={-1,1,0,0};
int Y[]={0,0,1,-1};

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int flag=0;
        int f1=0,f2=0,f3=0;
        if(n==1)
        {
            cout<<0<<endl;
            continue;
        }
        if(n==2)
        {
            cout<<-1<<endl;
            continue;
        }
        if(n==3)
        {
            cout<<2<<endl;
            continue;
        }
        int temp=n;
        for(int i=2; i<=sqrt(n); i++)
        {
            if(n%i==0)
            {
                if(i==2) f1=1;
                if(i==3) f2=1;

                else if(i>3) f3=1;
               // cout<<i<<endl;
                while(n%i==0)
                    n=n/i;
            }
        }
        if(n>1) f3=1;
      //  cout<<f2<<" "<<f3<<endl;
        if(f2==0 || f3==1)
        {
            cout<<-1<<endl;
            continue;
        }

        int cnt=0;
        while(temp>1)
        {
            if(temp%6==0)
            {
                temp=temp/6;
                ++cnt;
            }
            else
            {
                temp=temp*2;
                ++cnt;
            }
        }
        cout<<cnt<<endl;
    }
}


