Міша десь вичитав, що таке цифровий корінь числа: "\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 Для кожного прикладу вхідних даних виведіть у окремому рядку єдине число - відповідь на поставлену задачу.