재빠른 아기사슴

재빠른 아기사슴이 긴 도약으로 빈터를 향해 나아간다. 에너지가 넘쳐서 매 도약은 바로 앞 도약의 최대 두 배까지 길어질 수 있다.

좀 더 정확히 말하면, 어느 순간이든 아기사슴의 에너지는 특정한 준위 $i$에 있다. 아기사슴은 두 가지 방식으로 움직일 수 있다.

• 앞이나 뒤로 $i$미터만큼 도약한다. 이때 에너지 준위는 자동으로 $2i$로 바뀐다.
• 제자리에서 위로 도약한다. 이 도약은 빈터를 향한 경로 위에서 위치를 바꾸지 않으며, 에너지 준위를 $i/2$로 바꾼다.

처음에 아기사슴의 에너지는 $1$이다. 에너지가 $1$인 상태에서 위로 도약하면 아기사슴은 멈춘다.

아래 그림은 경로 왼쪽 지점에서 출발한 아기사슴의 이동 예시이다. 화살표 위의 숫자는 해당 도약 직후의 에너지 준위를 나타내며, 값 $0$은 아기사슴이 멈췄음을 뜻한다.

빈터로 이어지는 경로는 양방향으로 무한하다. 따라서 이동 도중 아기사슴은 빈터를 지나치거나 출발점보다 뒤로 갈 수도 있다. 처음에 아기사슴과 목표 지점 사이의 거리는 $n$미터이다. 아기사슴이 빈터에 도착해 그곳에서 멈추기 위해 필요한 최소 도약 횟수를 구하여라.

첫 번째이자 유일한 줄에 아기사슴과 빈터 사이의 거리를 나타내는 정수 $n$ ($1 \le n \le 10^{100}$)이 주어진다.

또한 전체 배점의 40%에 해당하는 테스트에서는 추가로 $n \le 100000$이 성립한다.

아기사슴이 빈터에 도착해 멈추기 위해 수행해야 하는 최소 도약 횟수를 정수 하나로 출력한다.