시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 89 22 21 41.176%

문제

치삼이는 정사각형의 종이 하나를 가지고 있다. 종이를 정확히 반으로 여러 번 잘라 같은 크기를 가진 종이를 N개 가지고 싶다. 치삼이가 자른 종이 크기의 종류는 최대 두 가지이다. 종이를 자를 때는 하나의 종이조각만을 자를 수 있다. (겹치거나 종이를 나란히 놓아 여러 개의 종이조각을 한번에 자를 수 없다.) 최대한 적은 수로 종이를 자르려 할 때 치삼이가 종이를 자르는 최소 횟수를 구하시오.

입력

치삼이가 필요한 종이의 개수 N이 주어진다. (1 ≤ N < 232)

출력

종이를 자르는 가장 적은 횟수를 출력한다.

예제 입력 1

13

예제 출력 1

14