А чим Міша гірший Васі та Даші?

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

Міша ввів свій термін: цифровий корінь $4$-го порядку - це описаний вище цифровий корінь, але знаходиться він по останнім $4$-м цифрам числа. Тому цифровий корінь $4$-го порядку для числа з прикладу вище дорівнює $8$.

Допоможіть Міші знайти цифровий корінь $4$-го порядку $k$-го числа Фібоначчі.

Нагадаємо, що числа Фібоначчі визначаються наступними рекурентними співвідношеннями: