include <bits/stdc++.h>

define gcd(a, b) __gcd(a, b)

define INF 0x3f3f3f3f3f

define eps 1e-6

define PI acos(-1.0)

define pb push_back

define fst first

define sec second

define eif else if

define de(x) cout << x << ' '

define en cout << '\n'

define fuck cout << "fuck\n"

define rep(i, x, y) for (int i = x; i < y; i++)

define red(i, x, y) for (int i = x - 1; i >= y; i--)

define mem(a, x) memset(a, x, sizeof(a))

define IOS cin.tie(0), ios::sync_with_stdio(false)

define maxn 200005

define mod 1000000007

typedef long long ll;

define pll pair<ll, ll>

using namespace std;
ll n, ans;
ll a[105];
ll count(ll x) {
ll cnt = 0;
while(x) {
cnt += (x & 1);
x >>= 1;
}
return cnt;
}
void dfs(ll x, ll sum, ll cnt) {
if(x == 16) {
//cout << x << endl;
ll res = n - sum;
ans = min(ans, count(res) + cnt);
return;
}
if(sum > n) return;
dfs(x + 1, sum, cnt);
if(x >= 3 && sum + a[x] <= n) dfs(x + 1, sum + a[x], cnt + 1);//避免2^0, 2^1与1!, 2!冲突
}
void solve() {
cin >> n;
ans = count(n);
a[1] = 1ll;
for(int i = 2; i <= 15; i++) {
a[i] = a[i - 1] * i;
}
dfs(1, 0, 0);
cout << ans << endl;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
}