var i := 1
proc hanoi (n, f, t, u : int)
    if n > 0 then
        hanoi (n - 1, f, u, t)
        put "move ", i, ": ", f, " to ", t
        i += 1
        hanoi (n - 1, u, t, f)
    end if
end hanoi
hanoi (6, 1, 3, 2)

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int f(int i){
  return (1 << i) - 1;
}

int main(){
  ifstream ifile("s5.in", ios::in);
  ofstream ofile("s5.out", ios::out);
  vector<int> g;
  // g(n) = min{ 2 * g(k) + f(n - k), 1 <= k < n }
  //         k
  g.push_back(0);
  g.push_back(1);

  for (int i = 2; i < 359; ++i){
    int j;
    int t = 2 * g[i - 1] + f(1);
    for (j = 2; j < i; ++j){
      int u = 2 * g[i - j] + f(j);
      if (u < t)
        t = u;
      else
        break;
    }
    g.push_back(t);
    //    ofile << i << ',' << j - 1 << ':' << t << endl;
  }
 
  int k;
  ifile >> k;
  while (k--){
    int n;
    ifile >> n;
    ofile << g[n] << endl;
  }
 
}

#include <stdio.h>
#include <stdlib.h>

#define threepoles(n) ((1 << (n)) - 1)

unsigned long cache[301] = {0};

unsigned long fourpoles(n) {
    unsigned long k, r, moves;
    if(cache[n]) return cache[n];

    r = 1;
    for(k=n-1; k>=1; k--) { // Start k large, so that threepoles(n-k) is small
   
        // Move k pieces on 4 poles, n-k pieces on 3 poles, then k pieces on 4 poles
        moves = 2 * fourpoles(k) + threepoles(n-k);
       
        // As k changes, the # of moves decreases then increases in a bimodal distribution
        // We want the first value that has no smaller value proceeding it (the smallest k)
        if(r==1 || moves < r) r = moves;
        else break; // Stop once we've found the smallest k value
                    // That optimization is necessary or else the program will fail when it 2^n-1 ifies large values of n
    }
    return cache[n] = r;
}

int main() {
    int n, t;
   
    freopen("s5.in", "rt", stdin);
    freopen("s5.out", "wt", stdout);
   
    scanf("%d\n", &t);
    while(t--) {
        scanf("%d\n", &n);
        printf("%d\n", fourpoles(n));
    }
   
    return 0;
}