Задачі
А чим Міша гірший Васі та Даши?
А чим Міша гірший Васі та Даши?
Міша десь вичитав, що таке цифровий корінь числа: "\textit{Якщо ми складемо усі цифри якого-небудь числа, потім усі цифри знайденої суми і будемо повторювати це багато разів, ми, нарешті, отримаємо однозначне число (цифру), яке називається цифровим коренем заданого числа. Наприклад, цифровий корінь числа }\textit{\textbf{34697}}\textit{ дорівнює }\textit{\textbf{2 (3+4+6+9+7=29}}\textit{; }\textit{\textbf{2+9=11}}\textit{; }\textit{\textbf{1 + 1=2}}\textit{).}"
Міша ввів свій термін: цифровий корінь \textbf{4}-го порядку - це описаний вище цифровий корінь, але знаходиться він по останнім \textbf{4}-м цифрам числа. Тому цифровий корінь \textbf{4}-го порядку для числа з прикладу вище дорівнює \textbf{8}.
Допоможіть Міші знайти цифровий корінь \textbf{4}-го порядку \textbf{k}-го числа Фібоначчі.
Нагадаємо, що числа Фібоначчі визначаються наступними рекурентними співвідношеннями:
\includegraphics{https://static.e-olymp.com/content/8d/8d15791d7578d6dfaaee44c65ebc7f8efa5e4414.jpg}
\InputFile
У кожному рядку вхідного файлу задано єдине число \textbf{k} (\textbf{0} ≤ \textbf{k} ≤ \textbf{9223372036854775807}).
\OutputFile
Для кожного прикладу вхідних даних виведіть у окремому рядку єдине число - відповідь на поставлену задачу.
Вхідні дані #1
0 1 2 37 14 135 23
Вихідні дані #1
1 1 2 6 7 3 5