Маленький Джон изучает числовые системы. После того как он все изучил о системах с фиксированным основанием, Джона заинтересовали другие, более необычные. Среди них он встретил \textit{систему Фибоначчи}, которая однозначно представляет все натуральные числа при помощи двух цифр: единицы и нуля. Но в отличии от обычной бинарной системы, в системе Фибоначчи нельзя ставить две единицы в соседние позиции. \includegraphics{https://static.e-olymp.com/content/04/043110503e347979317aaf18582fba8558c4b19d.jpg} Можно доказать, что если имеется число в системе Фибоначчи, то его значение равно \textbf{N = a_n·F_n + a_\{n-1\}·F_\{n-1\} + ... + a_1·F_1}, где \textbf{F_k} - последовательность Фибоначчи, задаваемая соотношениями \textbf{F_0 = F_1 = 1}, \textbf{F_i = F_\{i-1\} + F_\{i-2\}}. Например, первые несколько натуральных чисел имеют следующее представление в системе Фибоначчи: \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} Джон записал очень длинную строку (считайте что бесконечную), состоящую из представлений последовательных натуральных чисел в системе Фибоначчи. Например, первыми цифрами такой строки будут \textbf{110100101100010011010...} Джона интересует, сколько раз встречается цифра \textbf{1} в \textbf{N}-ом префиксе строки. Напомним, что \textbf{N}-\textit{ым префиксом }строки называется строка, состоящая из ее первых \textbf{N} символов. Напишите программу, которая подсчитает количество цифр \textbf{1}, которое встречается в \textbf{N}-ом префиксе строки Джона. \InputFile Одно целое число \textbf{N} (\textbf{0} ≤ \textbf{N} ≤ \textbf{10^15}). \OutputFile Вывести одно число - количество единиц в \textbf{N}-ом префиксе строки Джона.