Факториалом целого числа 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 до 10⁹.

Выходные данные

Натуральное число от 2 до 16 − ответ задачи.

Пример ввода 5 Пример вывода 7