unordered_map<int, int> m;
int calc( int n ) {  
  if (n == 1)
    return 0;
  int &res = m[n]; // 0 = default
  if (res != 0)
  res = calc(n) + 1; // n --> n-1
  if (n % 2 == 0)
    res = min(res, calc(n / 2) + 1);
  if (n % 3 == 0)
    res = min(res, calc(n / 3) + 1);
  return res;
}

int main() {
  int n;
  cin >> n;

  int f[n + 1];
  f[1] = 0; // Динамика назад
  for (int i = 2; i <= n; i++) {
    // i <- i-1, i/2, i/3
    f[i] = f[i - 1] + 1;
    if (i % 2 == 0)
      f[i] = min(f[i], f[i / 2] + 1);
    if (i % 3 == 0)
      f[i] = min(f[i], f[i / 3] + 1);
  }

  int g[3 * n + 1]; // Чтобы не было index out of range
  fill(g, g + n + 1, INT_MAX);
  g[1] = 1; // Динамика вперед
  for (int i = 1; i <= n; i++) {
    g[i + 1] = g[i + 1] + g[i];
    g[2 * i] = g[2 * i] + g[i];
    g[3 * i] = g[3 * i] + g[i];
  }

  m = new int[n + 1];
  fill(m, m + n + 1, -1);
  int result = calc(n);
}