Little John studies numeral systems. After learning all about fixed-base systems, he became interested in more unusual cases. Among those cases he found a \textit{Fibonacci system}, which represents all natural numbers in an unique way using only two digits: zero and one. But unlike usual binary scale of notation, in the Fibonacci system you are not allowed to place two \textbf{1}s in adjacent positions. \includegraphics{https://static.e-olymp.com/content/04/043110503e347979317aaf18582fba8558c4b19d.jpg} One can prove that if you have number in Fibonacci system, its value is equal to \textbf{N = a_n·F_n + a_\{n-1\}·F_\{n-1\} + ... + a_1·F_1}, where \textbf{F_k} is a usual Fibonacci sequence defined by \textbf{F_0=F_1=1}, \textbf{F_i=F_\{i-1\}+F_\{i-2\}}. For example, first few natural numbers have the following unique representations in Fibonacci system: \textbf{1 = 1_F} \textbf{2 = 10_F} \textbf{3=100_F} \textbf{4=101_F} \textbf{5=1000_F} \textbf{6=1001_F} \textbf{7=1010_F} John wrote a very long string (consider it infinite) consisting of consecutive representations of natural numbers in Fibonacci system. For example, the first few digits of this string are \textbf{110100101100010011010...} He is very interested, how many times the digit \textbf{1} occurs in the \textbf{N}-th prefix of the string. Remember that the \textbf{N}-\textit{th prefix} of the string is just a string consisting of its first \textbf{N} characters. Write a program which determines how many times the digit \textbf{1} occurs in \textbf{N}-th prefix of John's string. \InputFile The input file contains a single integer \textbf{N} (\textbf{0} ≤ \textbf{N} ≤ \textbf{10^15}). \OutputFile Output a single integer - the number of \textbf{1}s in \textbf{N}-th prefix of John's string.