#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<ll>
#define vld vector<ld>
#define all(a) a.begin(), a.end()
#define ull unsigned long long
#define endl '\n'
#define loop(i, n) for (int i = 0; i < (n); i++)
const ll MOD = 1e9 + 7;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

void fileio() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}
void read2d(vector<vector<int>>&arr,int n,int m) {
    for (int i =0;i<n;i++) {
        for (int j =0;j<m;j++) {
            cin>>arr[i][j];
        }
    }
}
void print2d(vector<vector<int>>&arr,int n,int m) {
    for (int i =0;i<n;i++) {
        for (int j =0;j<m;j++) {
            cout<<arr[i][j]<<" ";
        }
        cout<<'\n';
    }
}
void read1d(vector<int>&arr) {
    for (int i =0;i<arr.size();i++) {
        cin>>arr[i];
    }
}
void read1d(vector<ll>&arr) {
    for (int i =0;i<arr.size();i++) {
        cin>>arr[i];
    }
}
void print1d(vector<int>&arr) {
    for (int i =0;i<arr.size();i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
bool ispowerof2(ll n ) {
    return log2(n)-static_cast<long long>(log2(n))==0;
}
ll isafactorial(ll n) {
    ll i =2 ;
    long double m = static_cast<long double>(n);
    while (m>1) {
      m/=i;
        i++;
    }
    return  m==1 ? i : 0;

}

bool LinearSearch(vector<ll>& nums, ll val) {
    ll n = nums.size();
    for (ll i =0;i<n;i++) {
        if (nums[i]==val) {
            return 1 ;
        }
    }
    return 0;
}
ll cnt = LLONG_MAX;vector<ll>factorials;
int factorial(int n ) {
    if (n==1||n==0) {
        return 1 ;
    }
    return n * factorial(n-1);
}

void preprocessing() {
    for (ll i =1 ;i<=15;i++) {
        ll fact=factorial(i);
        factorials.push_back(fact);
    }
    for (ll i = 1 ;i<=39;i++) {
        factorials.push_back(pow(2,i));
    }
    factorials.erase(unique(all(factorials)),factorials.end());
}
void gen(ll i ,ll sum,ll op, ll n ) {
    if (i==factorials.size()) {
        return;
    }
    if (sum>n) {
        return;
    }
    if (sum==n) {
        cnt=min(cnt, op);
        return;
    }
    gen(i+1,sum,op,n);
    if (LinearSearch(factorials,factorials[i])) {
       gen(i+1,sum+factorials[i],op+1,n);
    }
}

void solve() {
  cnt = LLONG_MAX  ;  ll n ; cin>>n ;
    if (LinearSearch(factorials,n)) {
        cout<<1<<endl;
        return;
    }
    gen(0,0,0,n);
    cout<<cnt<<endl;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   fileio();
    preprocessing();
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}