// #include <algorithm>
#include <cstdio>
#include <unordered_map>
#include <vector>
using namespace std;

int n;
int ans;
unordered_map<int, bool> vis;
vector<int> use;
int k;

bool dfs(int now, int step) {
  // printf("[%d %d]\n", now, step);
  // if (step >= ans) return;

  if (step > k) return false;
  if (now < 0 || now > 2 * n) return false;

  if (now == n) {
    // ans = min(ans, step);
    // return;
    return true;
  }

  int siz = use.size();
  // printf("item: ");
  // for (auto x : use) printf("%d ", x);
  // printf("\n");
  // printf("[%d]", siz);
  for (int i = 0; i < siz; ++i) {
    int newnum = now + use[i];
    if (!vis[newnum]) {
      use.push_back(newnum);
      vis[newnum] = 1;
      if (dfs(newnum, step + 1)) return true;
      vis[newnum] = 0;
      use.pop_back();
    }

    newnum = now - use[i];
    if (!vis[newnum]) {
      use.push_back(newnum);
      vis[newnum] = 1;
      if (dfs(newnum, step + 1)) return true;
      vis[newnum] = 0;
      use.pop_back();
    }
  }

  return false;
}

int main() {
  freopen("pow_cal.in", "r", stdin);
  freopen("pow_cal.out", "w", stdout);
  while (scanf("%d", &n)) {
    if (!n) break;
    if (n == 1) {
      printf("0\n");
      continue;
    }
    // ans = 0x7fffffff;
    for (k = 1;; ++k) {
      vis.clear();
      use.clear();
      use.push_back(1);
      if (dfs(1, 0)) {
        printf("%d\n", k);
        break;
      }
      // printf("%d\n", ans);
    }
  }
  return 0;
}