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