Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача J. Без двух единиц подряд

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Артём и Женя играют в следующую игру: они по очереди называют натуральные числа в порядке возрастания, которые в своей двоичной записи не имеют двух единиц подряд. Такими числами, например, будут 1,2,4,5,8 и так далее. А вот числа 3=112, 6=1102 или 7=1112 игроки пропускают.

Артём только что назвал число n. Какое число следует назвать Жене, чтобы продолжить игру?

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

Единственная строка входных данных содержит натуральное число n. Гарантируется, что в его двоичном представлении нет двух единиц подряд.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

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

Ограничения

1n1017

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

В примере дано n=9=10012. Следующее число n+1=10=10102 тоже не имеет двух единиц подряд в своей двоичной записи.

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

Стандартный вход Стандартный выход
1
9
10

0.055s 0.011s 13