KUPC2015_H.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;

const ll INF = 1e17;

map<pair<ll,int>,ll> memo;

ll dp(ll n, int m) {
  if (m > 100) return INF;
  if (n == 0) {
    if (m == 0) return 0;
    else return INF;
  }
  pair<ll,int> p = make_pair(n, m);
  if (memo.count(p)) return memo[p];
  ll res = INF;
  if (n % 2 == 0) {
    res = min(res, dp(n/2, m) * 2);
  }
  else {
    res = min(res, dp((n+1)/2, m+1)*2+1);
    res = min(res, dp(n/2, m-1)*2);
  }
  return memo[p] = res;
}

int main() {
  int q; cin >> q;
  while (q--) {
    ll n; cin >> n;
    memo.clear();
    cout << dp(n, 0) << endl;
  }
  return 0;
}