Задача A. Шахматные пушки ≡

Условие

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

По мнению юного шахматиста, пешка — слишком слабая фигура. Для её усиления Пашка разрешает ей бить по диагонали на любое количество клеток (но, по-прежнему, только вперёд). Новую фигуру мальчик называет пушкой и старательно исследует её свойства.

Помогите мальчику определить, сколько белых пушек достаточно, чтобы контролировать все поля шахматной доски размером n × n. Других фигур на доске нет. Считайте, что пушка контролирует и ту клетку, на которой стоит.

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 8, получат не менее 35 баллов.

Решения, верно работающие при n ≤ 10⁵, получат не менее 70 баллов.

Пояснение к примеру

Смотри рисунок. Пушки на нижней горизонтали бьют все поля кроме b3. Добавим туда четвёртую пушку. Меньшим количеством фигур обойтись нельзя.

Примеры тестов

3

4