18124번 - 치삼이의 종이 자르기

문제

치삼이는 정사각형의 종이 하나를 가지고 있다. 종이를 정확히 반으로 여러 번 잘라 같은 크기를 가진 종이를 N개 가지고 싶다.

치삼이는 종이 크기의 종류가 두 가지가 넘으면 복잡해서 머리가 아프다. 따라서 치삼이가 자른 종이 크기의 종류는 두 가지를 넘을 수 없다.

위의 주어진 그림의 종이에 붙여진 숫자는 종이 크기의 종류를 의미한다. 같은 숫자가 붙은 종이는 같은 크기이다.

가장 오른쪽 그림은 치삼이가 가지고 있는 종이 크기의 종류가 2가지를 넘어가서 치삼이가 머리가 아프다.

종이는 한 번에 하나의 종잇조각만을 자를 수 있다. 겹치거나 종이를 나란히 놓아 여러 개의 종잇조각을 한 번에 자를 수 없다.

같은 크기의 종이를 최소 N개 얻고 싶을 때, 치삼이가 종이를잘라야 하는 횟수의 최솟값을 구해보자.

입력

치삼이가 필요한 종이의 개수 N이 주어진다. N은 양의 정수이다. (1 ≤ N < 2³²)

출력

종이를 자르는 최소 횟수를 출력한다.

제한

힌트