고대 달력

바시는 최근 베를란드 학자들이 사라진 아프렐리야 원주민의 고대 달력을 발견했다는 기사를 읽었다. 이 달력은 다른 많은 고대 달력과 마찬가지로 머지않은 세계 종말을 예언했다.

원주민들은 신성한 수를 바탕으로 달력을 만들었다. 0번째 신성한 수는 1이고, 1번째 신성한 수도 1이다. 그다음 신성한 수 $F_i$는 바로 앞의 두 수의 합이다: $F_i = F_{i-1} + F_{i-2}$.

모든 자연수는 $F_i$ ($i > 0$)들의 합으로 나타낸다. 이때 합에 $F_j$가 들어 있으면 $F_{j-1}$과 $F_{j+1}$은 들어갈 수 없다. 이 표기법에서 예를 들어 16은 100100으로 쓴다. $16 = 1 \cdot 13 + 0 \cdot 8 + 0 \cdot 5 + 1 \cdot 3 + 0 \cdot 2 + 0 \cdot 1$이기 때문이다.

자연수 $i$의 이 표기를 $f\{i\}$라 하자. 달력은 모든 자연수의 표기를 1부터 차례로 이어 붙인 문자열 $S = f\{1\}f\{2\}f\{3\}\dots$이다.

바시는 달력의 첫 글자부터 $N$번째 글자까지에 연속한 0 두 개로 이루어진 묶음이 몇 개 있는지 구해 달라고 부탁한다.

입력 파일에는 정수 $N$ ($1 \le N \le 10^{18}$)이 한 개 주어진다. 바시가 관심을 갖는 마지막 글자의 번호이다.

달력의 처음 $N$개 글자에서 연속한 0 두 개가 나타나는 횟수를 한 줄로 출력한다.

달력의 처음 20글자는 11010010110001001101이다.