А чим Міша гірший Васі та Даши?
Міша десь вичитав, що таке цифровий корінь числа: "Якщо ми складемо усі цифри якого-небудь числа, потім усі цифри знайденої суми і будемо повторювати це багато разів, ми, нарешті, отримаємо однозначне число (цифру), яке називається цифровим коренем заданого числа. Наприклад, цифровий корінь числа 34697 дорівнює 2 (3+4+6+9+7=29; 2+9=11; 1 + 1=2)."
Міша ввів свій термін: цифровий корінь 4-го порядку - це описаний вище цифровий корінь, але знаходиться він по останнім 4-м цифрам числа. Тому цифровий корінь 4-го порядку для числа з прикладу вище дорівнює 8.
Допоможіть Міші знайти цифровий корінь 4-го порядку k-го числа Фібоначчі.
Нагадаємо, що числа Фібоначчі визначаються наступними рекурентними співвідношеннями:
Вхідні дані
У кожному рядку вхідного файлу задано єдине число k (0 ≤ k ≤ 9223372036854775807).
Вихідні дані
Для кожного прикладу вхідних даних виведіть у окремому рядку єдине число - відповідь на поставлену задачу.