eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

А чем Миша хуже Васи и Даши?

А чем Миша хуже Васи и Даши?

Лимит времени 0.5 секунд
Лимит использования памяти 8 MiB

Миша где-то вычитал, что такое цифровой корень числа: "Если мы сложим все цифры какого-либо числа, затем все цифры найденной суммы и будем повторять это много раз, мы, наконец, получим однозначное число (цифру), называемое цифровым корнем данного числа. Например, цифровой корень числа 34697 равен 2 (3+4+6+9+7=29; 2+9=11; 1 + 1=2)."

Миша ввёл своё понятие: цифровой корень 4-го порядка - это описанный выше цифровой корень, но находится он по последним 4-м цифрам числа. Поэтому цифровой корень 4-го порядка для числа из примера выше равен 8.

Помогите Мише найти цифровой корень 4-го порядка k-го числа Фибоначчи.

Напомним, что числа Фибоначчи определяются следующими рекуррентными соотношениями:

Входные данные

В каждой строке входного файла задано единственное число k (0k9223372036854775807).

Выходные данные

Для каждого примера входных данных выведите в отдельной строке единственное число - ответ на поставленную задачу.

Пример

Входные данные #1
0
1
2
37
14
135
23
Выходные данные #1
1
1
2
6
7
3
5
Автор Анатолий Присяжнюк
Источник 2-й этап Всеукраинской олимпиады по информатике 2013-2014 уч.г. 10 кл. г. Бердичев