Розглянемо ланцюжок, який скадається з N кілець. Яку мінімальну кількість кілець необхідно розцепити, щоб із кусочків, що залишаться, можна було б зібрати ланцюжки довільної довжини від 1 до N кілець? При створенні нових ланцюжків можна використовувати розцеплені кільця.
Наприклад, при N = 21, достатньо розцепити усього 2 кільця таким чином, щоб утворились ланцюжки довжиною 3, 5 та 11. Два розцеплених кільця важаються ланцюжками одиничної довжини.
Напишіть програму, яка за натуральним числом N - довжині початкового ланцюжка, знаходить мінімальну кількість кілець, які необхідно розцепити для досягнення описаної мети.
Одне ціле число N (1 ≤ N ≤ 10^9).
Вивести одне ціле число - знайдену мінімальну кількість кілець.