droot

Doamne, ce m-a speriat problema asta...

Lexi își amintește criteriile de divizibilitate de anul trecut și observă că unele implică aflarea sumei cifrelor unui număr. Notăm cu $\texttt{sumc}(n)$ suma cifrelor numărului natural $n$. După ce explorează puțin operația $\texttt{sumc}$, observă că, dacă aplică $\texttt{sumc}$ de suficiente ori, obține un număr cu o singură cifră. Notăm în continuare cu $\texttt{cif}(n)$ cifra obținută după aplicarea repetată a operației $\texttt{sumc}$. De exemplu, $\texttt{cif}(2026) = 1$, pentru că $\texttt{sumc}(2026) = 2 + 0 + 2 + 6 = 10$, iar $\texttt{sumc}(10) = 1 + 0 = 1$.

Lexi este interesată de comportamentul operației $\texttt{cif}$ față de șirul lui Fibonacci: $1$, $1$, $2$, $3$, $5$, $8$, $13$, $\ldots$ (definit riguros mai jos).

Cerință

Pentru a putea continua studiul operației $\texttt{cif}$, Lexi îți cere să scrii un program care să rezolve următoarele cerințe.

1. Se dă un număr natural $n$. Calculează $\texttt{cif}(n)$.
2. Se dă un număr natural $n$. Calculează $\texttt{cif}(f_1 + f_2 + \ldots + f_n)$, adică cifra obținută prin aplicarea operației $\texttt{cif}$ pe suma primilor $n$ termeni din șirul lui Fibonacci.

Date de intrare

Pe prima linie a fișierului de intrare droot.in se găsesc două numere naturale, $c$ (cerința de rezolvat) și $n$ (cu semnificația de mai sus).

Date de ieșire

Pe prima linie a fișierului de ieșire droot.out se va găsi o singură cifră, răspunsul la cerința $c$.

Restricții și precizări

• Șirul lui Fibonacci este $(f_n)_{n\geq 1}$, unde $f_1 = f_2 = 1$, iar $f_{n} = f_{n-1} + f_{n-2}$, pentru oricare $n \geq 3$.

Exemplul 1

droot.in

1 4052

droot.out

2

Explicație

Primul număr citit este $1$, deci se rezolvă cerința $1$.
$\texttt{cif}(4052) = 1$, pentru că $\texttt{sumc}(4052) = 4 + 0 + 5 + 2 = 11$, iar $\texttt{sumc}(11) = 1 + 1 = 2$.

Exemplul 2

droot.in

2 9

droot.out

7

Explicație

Primul număr citit este $2$, deci se rezolvă cerința $2$.
$f_1 + f_2 + \ldots + f_9 = 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88$.
$\texttt{cif}(88) = 7$, pentru că $\texttt{sumc}(88) = 8 + 8 = 16$, iar $\texttt{sumc}(16) = 1 + 6 = 7$.