배틀 봇

당신은 Battle-bots Aggressive Power Contest에 참가하고 있다. 각 팀이 다른 로봇과 싸울 로봇을 만들고, 상대 로봇을 파괴하면 이기는 토너먼트이다. 구체적으로는 상대 로봇의 유일한 모터가 파괴되어 더 이상 움직이지 않을 때 이긴다.

봇에는 무기가 두 가지 있다. 검은 상대 봇을 반으로 자를 수 있고, 발톱은 상대 봇에서 덩어리를 떼어 내 고철로 짓이길 수 있다. 두 공격은 걸리는 시간이 같다. 봇을 제어하는 프로그램은 항상 실행 중이며, 다음에 어떤 공격을 쓸지 결정한다.

봇이 검으로 상대를 반으로 자르면, 모터가 있는 쪽 절반은 계속 움직이므로 나머지 절반은 무시해도 된다. 봇이 발톱을 쓰면 상대 봇에서 크기 $1$의 덩어리가 떨어져 나간다. 그러나 상대 봇을 완전히 없애지 못한다면, 모터는 아직 발톱으로 건드리지 않은 조각에 있다고 가정하고 계속 싸워야 한다.

예를 들어 두 번째 예시 상황을 보자. 상대 봇이 너무 커서 발톱 공격을 5번 해야 완전히 부술 수 있다고 하자. 다음과 같이 움직일 수 있다. 먼저 검으로 베어 $2\frac12$ 크기의 두 조각으로 나눈다. 이어서 아직 움직이고 있는 조각에 발톱을 써서 $1\frac12$로 줄인다. 그 조각을 다시 검으로 반으로 잘라 $\frac34$로 만든다. 마지막으로 움직이는 조각을 발톱으로 짓이긴다. 이 방법이면 공격 4번으로 상대를 이길 수 있다.

당신의 봇에는 마이크로초당 구골(googol) 개의 공격 패턴을 쉽게 시뮬레이션하는 양자 컴퓨터가 탑재되어 있다. 그러나 가장 빠른 공격 패턴이 무엇인지 모르면, 그 패턴에 도달했는지도 알 수 없으므로 탐색을 멈추지 못한다.

상대를 쓰러뜨리는 데 발톱 공격이 몇 번 필요한지 주어졌을 때, 최악의 경우 상대를 쓰러뜨리는 데 필요한 공격 횟수의 최솟값을 구하는 프로그램을 작성하라.

한 줄에 정수 $n$ ($1\leq n\leq 10^{18}$)이 주어진다. $n$은 상대 봇을 쓰러뜨리는 데 필요한 발톱 공격 횟수이다.

상대 봇을 파괴하는 데 필요한 공격 횟수의 최솟값을 출력한다.