#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define nl "\n"
#define OO 0x3f3f3f3f
using namespace std;

void ta2to2a()
{
    ios_base::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
ll n;
vector<ll> v(55);
set<ll> powerfulNumbers()
{
    set<ll> st;
    for (int i = 0; i <= 41; i++)
    {
        st.insert(1LL << i);
    }
    ll x = 1LL;
    for (int i = 1; i <= 15; i++)
    {
        x *= i;
        st.insert(x);
    }

    return st;
}
ll powerfulSum(int i, ll sum, ll nums)
{
    if (sum == n)
    {
        return nums;
    }
    if (i == 55 || sum + v[i] > n)
    {
        return LONG_LONG_MAX;
    }
    ll ans1 = powerfulSum(i + 1, sum + v[i], nums + 1);
    ll ans2 = powerfulSum(i + 1, sum, nums);
    return min(ans1, ans2);
}
void solve()
{
    cin >> n;
    ll ans = powerfulSum(0, 0, 0);
    cout << ((ans == LONG_LONG_MAX) ? -1 : ans) << nl;
}
int main()
{
    ta2to2a();
    int t = 1;
    cin >> t;
    int i = 0;
    for (auto it : powerfulNumbers())
    {
        v[i] = it;
        i++;
    }
    while (t--)
    {
        solve();
    }
}