Поликарп и его коллеги празднуют завершение работы над инновационной системой защиты от кибератак. Над системой трудилось множество людей, Поликарп был ответственным за криптографическую часть. Одним из алгоритмов, разработанных им, является поиск случайного простого числа, не превосходящего N. Напомним, что простым числом является число, имеющее ровно два различных делителя — единица и само число.

Алгоритм поиска простого числа, написанный Поликарпом, выглядит так:

1. Выбрать случайное число x из отрезка [2, N]. Для всех N - 1 чисел вероятности быть выбранными одинаковы.
2. Проверить, является ли x простым. Если да, перейти к шагу 3, иначе к шагу 1.
3. Возвратить x как результат.

Проверку того, является ли число x простым, Поликарп реализовал отдельно. Он пользовался тем, что для составного числа всегда существует делитель, не превосходящий квадратного корня из x и при этом отличный от единицы. Это позволяет сэкономить вычисления.

Алгоритм проверки реализован следующим образом:

1. Положить d:  = 2.
2. Если d превосходит квадратный корень из x, то есть d² > x, то завершить работу алгоритма и сообщить, что x — простое число. Иначе перейти к шагу 3.
3. Проверить, делится ли x на d без остатка. Если да, завершить проверку, сообщив, что x — не простое. Иначе положить d:  = d + 1 и перейти к шагу 2.

Но сегодня Поликарп не мог уснуть. Его беспокоила мысль о том, что его алгоритм поиска может работать вечно! Или хотябы просто долго. А ведь это ставит под угрозу работу их системы.

Самой тяжёлой операцией Поликарп считает деление в проверке на простоту на третьем шаге. Посчитайте математическое ожидание количества этих делений по заданному N.