자석 절단

문제

근수는 길이가 64cm인 자석 막대 하나를 가지고 있다. 이 막대를 이용해 정확히 길이가 Xcm인 자석을 만들려고 한다.

자석은 다음과 같은 과정으로 자른다.

1. 가지고 있는 모든 자석의 길이 합을 구한다. 처음에는 64cm 자석 하나뿐이다. 합이 X보다 크면 다음 과정을 반복한다.
   1. 가장 짧은 자석을 절반으로 자른다.
   2. 자른 절반 중 하나를 버려도 남은 자석의 길이 합이 X 이상이라면, 그 절반을 버린다.
2. 남은 자석들을 모두 이어 붙여 Xcm를 만든다.

X가 주어졌을 때, 위 과정을 거치면 몇 개의 자석 조각이 필요한지 구하라.

참고로 이 과정은 항상 성공하며, Xcm를 만들기 위한 최소 조각 수를 보장한다.

입력

첫째 줄에 만들고자 하는 자석의 길이 X가 주어진다. (1 ≤ X ≤ 64, 정수)

출력

위 과정을 거친 후 남은 자석 조각의 개수를 출력한다.

입출력 예시

입력 1

23

출력 1

4

입력 2

32

출력 2

1

입력 3

64

출력 3

1

입력 4

48

출력 4

2