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

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

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

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

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

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

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

10

8