Солдатики в квадратике

У Гриши есть N солдатиков. Недавно он понял, что хочет выставить ВСЕХ своих солдатиков в квадратный строй (так, чтобы количество рядов было равно количеству солдатиков в ряду). Но, как оказалось, не всегда он сможет это сделать. К счастью, у него есть друг Миша, у которого есть целых ∞ солдатиков. Он предложил Грише такую сделку: Гриша называет натуральное число M, платит Мише M монет, и Миша дает ему столько солдатиков, чтобы у него их стало N*M.
Подскажите Грише, какое минимальное количество монет ему придется заплатить своему другу, чтобы он смог исполнить свою затею.

Формат файла входных данных:
Натуральное число N - количество солдатиков у Гриши. (N <= 2*1018).

Формат файла выходных данных:
Минимальное количество монет, которое придется заплатить Грише.

Пример:
input.txt output.txt
12 3
Помогите решить задачку на питоне или паскале.

0

предполагаю тут бин.поиск по ответу, но условие какое то "корявое".

0