Факториалом целого числа N
(обозначается N!) называется произведение 1 ∙ 2 ∙ 3 ∙
... ∙ N. Например, 5! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120.
Нетрудно сообразить, что при N ≥ 5 число N! всегда
заканчивается хотя бы одним нулём.
Можно заметить, что количество
нулей на конце факториала зависит от того, в какой системе счисления его
записать. Например, 5! в двоичной системе счисления запишется как 1111000 и будет
оканчиваться уже не одним, а тремя нулями. Это же число в семеричной системе
счисления запишется как 231, и вообще не будет иметь нулей в конце.
Дано натуральное число N.
Найдите основание системы счисления в диапазоне от 2 до 16, при котором запись
числа N! заканчивается наименьшим числом нулей. При наличии нескольких правильных
ответов выведите наименьший из них.
Входные данные
Натуральное число N в диапазоне от 1 до 109.
Выходные данные
Натуральное
число от 2 до 16 − ответ задачи.
|
Пример ввода
5
Пример вывода
7
|
