Задача B. Факториал и Аля ≡

Условие

Сегодня Аля на занятии кружка по математике узнала, что такое факториал. В качестве учебного проекта она выбрала разбор и решение следующей задачи: "Определить последнюю ненулевую цифру факториала данного числа $n$". Да вот только не получается у неё что-то. Помогите Але!

Формат входных данных

Единственная строка входного файла содержит натуральное число $n$.

Формат выходных данных

Выведите одну десятичную цифру — ответ на вопрос задачи.

Ограничения

$1 \le n \le 10^{5}$

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при $n \le 18$, получат не менее 20 баллов.

Пояснение к примеру

В примере дано $n = 10$. Факториал числа 10 равен $1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 = 3628800$. Последняя ненулевая цифра 8.

Примеры тестов

10

8