В далекой-далекой галактике снова война. Коварная Республика нанесла k точечных ударов силы ai по владениям Империи. Чтобы справиться с республиканской угрозой верховный совет постановил нанести решающий удар по силам противника.
Для успешного завершения конфликта баланс противостояния после нанесения этого удара должен быть целым положительным числом. Балансом противостояния называется число, вида 
, где p = n! (n — сила удара Империи), 
. После многих лет войны ресурсы Империи истощены, поэтому для уменьшения затрат n должно быть минимальным целым положительным числом, удовлетворяющим командование.
Помогите Империи, найдите минимальное целое положительное n, при котором описанная дробь является целым положительным числом.
Выходные данные
Выведите минимальное целое положительное число n, необходимое для победы Империи.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1000 1000
|
2000
|
|
2
|
1
2
|
2
|