And how is Misha worse than Vasya and Dasha?#5720
Misha recently learned about the concept of a digital root: "If you sum all the digits of a number, then sum the digits of the resulting sum, and continue this process repeatedly, you will eventually arrive at a single-digit number, known as the digital root of the original number. For instance, the digital root of the number 34697 is 2 (3+4+6+9+7=29; 2+9=11; 1+1=2)."
Misha came up with his own idea: the digital root of the th order. This is similar to the digital root described above, but it is calculated using only the last digits of the number. Therefore, for the number in the example above, the digital root of the th order is .
Your task is to help Misha find the digital root of the th order for the -th Fibonacci number.
Recall that Fibonacci numbers are defined by the following recurrence relations:
Each line of the input file contains a single number (0 \le k \le 9223372036854775807).
For each input case, output a single number on a separate line, which is the solution to the problem.
Example 1