시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 124 60 48 48.980%

문제

0과 1로 구성된 이진수가 있다. 이 이진수에서 0을 10으로, 1을 01로 동시에 치환하면 길이가 두 배인 이진수를 얻을 수 있다. 이러한 이진수들을 차례로 나열하면 하나의 이진수 수열이 된다. 편의상 시작 수는 1이라고 하자. 처음 몇 개의 이진수들을 구해 보면,

1 -> 01 -> 1001 -> 01101001 -> …

이 된다.

N이 주어졌을 때, N번째 이진수에서 연속된 0들의 그룹이 몇 개나 있는지 알아내는 프로그램을 작성하시오. N=4일 경우의 이진수는 01101001이고, 따라서 이 안에는 연속된 0들이 세 그룹 있게 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력

3

예제 출력

1

힌트