A. Разрезание на части
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть прямоугольный лист бумаги, который он хочет разделить ровно на $$$n$$$ частей.

Для этого он может производить два типа разрезов:

  • горизонтальный разрез, который начинается с левой стороны листа, заканчивается в правой стороне листа, проходя через весь лист параллельно верхней и нижней стороне листа;
  • вертикальный разрез, который начинается с верхней стороны листа, заканчивается в нижней стороне листа, проходя через весь лист параллельно левой и правой стороне листа.

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

Перед вами стоит задача определить минимальное суммарное количество горизонтальных и вертикальных разрезов, которые должен сделать Монокарп, чтобы разделить лист на ровно $$$n$$$ частей.

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

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 1\,000\,000$$$) — количество частей, которые должны получиться.

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

Выведите минимальное суммарное количество горизонтальных и вертикальных разрезов, которые должен сделать Монокарп, чтобы разделить лист на ровно $$$n$$$ частей.

Примеры
Входные данные
8
Выходные данные
4
Входные данные
3
Выходные данные
2
Входные данные
100
Выходные данные
18
Примечание

В первом примере Монокарп может, например, сделать три горизонтальных разреза и один вертикальный разрез. После этого лист будет разделен на $$$8$$$ частей суммарно за четыре разреза.

Во втором примере Монокарп может, например, сделать два вертикальных разреза. После этого лист будет разделен на $$$3$$$ части за два разреза.

В третьем примере Монокарп должен сделать девять вертикальных разрезов и девять горизонтальных разрезов. После этого лист будет разделен на $$$100$$$ частей суммарно за $$$18$$$ разрезов.