#include <string>
#include <deque>
#include <map>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define VIT(i, v) for (i = 0; i < v.size(); i++) 
#define IT(it, ds) for (it = ds.begin(); it != ds.end(); it++)
#define O1(v) cout << v << endl
#define O2(v1, v2) cout << v1 << " " << v2 << endl
#define O3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << endl
#define OVEC(v) { int iii; VIT(iii, v) cout << v[iii] << " " ; cout << endl; }

class EmoticonsDiv1 {
  public:
    int printSmiles(int smiles);
};

int EmoticonsDiv1::printSmiles(int smiles)
{
  deque <string> BFSQ;
  map <string, int> Shortest_Paths;
  int emoticons;
  int clipboard;
  int seconds;
  char buf[100];
  string s, s2;

  /* Put the starting state on the BFSQ. */

  Shortest_Paths["1,0"] = 0;
  BFSQ.push_back("1,0");

  while (1) {

    /* Grab the first node off the BFSQ.  
       Turn the node name into emoticons & clipboard, and
       then get the number of seconds from the Shorest_Paths map.
       If the emoticons is our target, then we're done -- return 
       the number of seconds. */

    s = BFSQ[0];
    BFSQ.erase(BFSQ.begin());
    sscanf(s.c_str(), "%d,%d", &emoticons, &clipboard);
    seconds = Shortest_Paths[s];
    if (emoticons == smiles) return seconds;
    
    /* Create a new node by copying the emoticons into
       the clipboard.  If this node doesn't exist, create it and put
       it onto the BFSQ. */

    sprintf(buf, "%d,%d", emoticons, emoticons);
    if (Shortest_Paths.find(buf) == Shortest_Paths.end()) {
      Shortest_Paths[buf] = seconds+1;
      BFSQ.push_back(buf);
    }

    /* Create a new node by pasting the clipboard.  Only do this
       if the number of emoticons is less than the target. 
       Put this onto the BFSQ if the node doesn't exist yet. */

    if (emoticons < smiles) {
      sprintf(buf, "%d,%d", emoticons+clipboard, clipboard);
      if (Shortest_Paths.find(buf) == Shortest_Paths.end()) {
        Shortest_Paths[buf] = seconds+1;
        BFSQ.push_back(buf);
      }
    }

    /* Finally, create a new node by deleting one emoticon.  If the
       result is a positive number, then put it on the BFSQ. */

    if (emoticons > 1) {
      sprintf(buf, "%d,%d", emoticons-1, clipboard);
      if (Shortest_Paths.find(buf) == Shortest_Paths.end()) {
        Shortest_Paths[buf] = seconds+1;
        BFSQ.push_back(buf);
      }
    }
  }

  /* We should never get here. */
  return -1;
}