The first who came closest

to solving the mystery of time

measurement on the planet Earth

was a great Fibonacci, though perhaps

he himself had no idea about it....

Find the last digit of the k-th Fibonacci number.

Fibonacci numbers are defined by the following recurrence relations:

Input

Each line contains a single number k (0 ≤ k ≤ 9223372036854775807).

Output

For each test case print in a separate line the last digit of the k-th Fibonacci number.