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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
10
8

0.092s 0.025s 15