#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll I=1e18,N=1e15;
void ad(ll &x,ll y){x=min(x,y);}
ll f[110],c[110];
ll n=100;
int m;
struct qb{ll x,b,k;}e[100100];
ll C(ll x){
    ll su=0;
    for(int i=0;(1ll<<i)<=x;i++)
    su+=(min(x,(1ll<<(i+1))-1)-(1ll<<i)+1)*(i+1);
    return su;
}
bool bj;
ll F(ll x){
    int l=1,r=m,jx=-1;
    while(l<=r){
        int mi=(l+r)>>1;
        if(e[mi].x<=x)jx=mi,l=mi+1;
        else r=mi-1;
    }
    return e[jx].b+(x-e[jx].x)*e[jx].k;
}
ll F_(ll x){
    ll l=2,r=x-1,ox=1;
    while(l<=r){
        ll mi=(l+r)>>1,m_=mi-1;
        ll t_=F(m_)+F(x-m_)+C(m_),t=F(mi)+F(x-mi)+C(mi);
        if(t_>t)ox=mi,l=mi+1;
        else r=mi-1;
    }
    return F(ox)+F(x-ox)+C(ox)+C(x);
}
int main(){
    f[0]=0,f[1]=c[1]=1;
    m=1,e[1]=(qb){0,0,1};
    for(int i=2;i<=n;i++){
        f[i]=I;c[i]=c[i-1]+1+((int)log2(i));
        for(int j=1;j<i;j++)if(f[i]>=f[j]+f[i-j]+c[j])
        f[i]=f[j]+f[i-j]+c[j];
        if(f[i]>f[i-1]+1)f[i]=f[i-1]+1;
        f[i]+=c[i];
        if(f[i]-f[i-1]!=f[i-1]-f[i-2])e[++m]=(qb){i-1,f[i-1],f[i]-f[i-1]};
    }
    while(e[m].x<N){
        ll l=e[m].x+1,r=N,wh=N+1;
        while(l<=r){
            ll mi=(l+r)>>1;
            if(F_(mi)>e[m].b+(mi-e[m].x)*e[m].k)wh=mi,r=mi-1;
            else l=mi+1;
        }
        if(wh==N+1)break;
        ll ct=F_(wh),f0=e[m].b+(wh-1-e[m].x)*e[m].k;
        e[++m]=(qb){wh-1,f0,ct-f0};
    }
    int T;scanf("%d",&T);while(T--){
        scanf("%lld",&n);bj=1;
        printf("%lld\n",F(n));
    }
    return 0;
}