И снова цепочка

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

Например, при N = 21, достаточно расцепить всего 2 кольца таким образом, чтобы получились куски длинной 3, 5 и 11. Два расцепленных кольца считаются кусками единичной длины.

Напишите программу, которая по натуральному числу N – длине исходной цепочки, находит минимальное количество колец, которые необходимо расцепить для достижения описанной цели.

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

Одно целое число N (1 ≤ N ≤ 10^9).

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

Вывести одно целое число - найденное минимальное количество колец.

Примеры