문제

상혁이는 어느 날 길을 걷다 트럭에 치이고 말았다.

낯선 곳에서 눈을 뜬 상혁이는 용사의 모습을 하고 있었다.

무슨 일이 일어난 건지 미처 생각하기도 전에, 눈 앞에 큰 슬라임 한 마리가 나타났다!

상혁이는 슬라임들 중 한 마리를 골라 공격을 할 수 있고, 해당 슬라임의 크기 에 따라 다음과 같은 일이 일어난다.

• 가 이라면, 해당 슬라임을 제거한다.
• 가 보다 크다면, 크기 의 슬라임 두 마리가 생성되고, 원래 슬라임은 제거된다.

(는 를 넘지 않는 가장 큰 정수를 가리킨다.)

공격이 끝났을 때 모든 슬라임이 제거된 상태라면 전투에서 이기게 된다.

전투를 시작하기 전에는 크기 의 슬라임 한 마리만 존재한다.

이 슬라임의 크기 가 주어질 때, 상혁이가 전투에서 이기기 위한 최소 공격 횟수를 구하시오.

입력

첫째 줄에 슬라임의 크기 가 주어진다. (, 는 정수)

출력

첫째 줄에 상혁이가 전투에서 이기기 위한 최소 횟수를 출력한다.

노트

의 범위가 C/C++, Java의 int 자료형으로 표현 가능한 범위를 넘어갈 수 있음에 유의하라.

예제 설명

첫 번째 예제에서, 상혁이가 먼저 크기가 인 슬라임을 공격하면, 크기가 인 슬라임 두 마리가 남게 된다. 이후, 두 마리의 크기 1의 슬라임을 각각 공격하면 총 번의 공격으로 모든 슬라임을 제거할 수 있다.