메뉴 건너뛰기

문제

00b29 벌집대소동 0  

시간메모리제출 올바른 답 비율
1초64MB
177
65
36.7%


나의 횟수나의 최근 판정시도 성공 비율
6050
83.3%
벌집대소동  

꿀벌인 마야는 세상에 처음으로 태어났다. 처음에는 애벌레였다가 차츰 차츰 자라서 꿀벌로 자라게 되었다. 꿀벌들의 세계는 매우 복잡하고 효율적으로 돌아갑니다. 모든 꿀벌들은 저마다의 임무가 주어진다. 채집을 잘하는 벌은 벌집 밖으로 나가서 꿀을 모으고, 애벌레는 잘 돌보는 꿀벌에게는 보모의 역할이 주어진다. 꿀벌들의 방은 정육각형의 구조로 되어있다. 모든 꿀벌들은 알은 상태에서 1번방에서 자라나면서 다른 방으로 차츰 옮기게 된다. 

마야에게 처음 내려진 임무는 이 복잡한 벌집에서 갓 알에서 태어난 애벌레를 정해진 방으로 안내하는 것이다. 여기서 마야는 제일 처음 애벌레에게 안내해야 할 것은 방을 몇 번이나 거쳐야하는지 알려주어야 한다. (항상 가는 경로는 최소의 횟수를 보장함)

만약 애벌레에게 17번방으로 안내해야 한다면 1번방에서 6번방을 거쳐 17번방으로 거쳐야 한다고 말해야 한다. 이때 거치는 방의 수는 1번방을 포함하여 총 3개를 거치게 된다.  

또 다른 예를 들면, 35번방으로 가는 애벌레에게는 1번->7번->18번->35번으로 총 4번의 방을 거쳐야 한다고 알려줘야 한다.  하지만 아직 초보인 마야는 걱정이 된다. 이미 여러 번의 실수로 인해 애벌레들이 자신의 방을 못 찾는 소동이 일어났기 때문이다.

번호가 커질수록 방을 몇 개나 거쳐야 하는지 헷갈리기 때문에 여러분들이 마야를 도울 수 있는 방법을 찾을 수 있도록 지혜를 모아야 할 때이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

1번방을 포함해 거쳐야하는 방의 수를 출력한다.

예시
1입력
35
출력
4
위로