Двоичные палиндромы

Ваша задача — найти наименьший двоичный палиндром, который не меньше заданного числа n. Двоичный палиндром — это число, которое в двоичной системе счисления читается одинаково как слева направо, так и справа налево. Например, числа 5, 7, 9 и 21 являются двоичными палиндромами, а числа 4, 10 и 11 — нет.

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

На первой строке вводится число n.

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

Выведите наименьший двоичный палиндром, который не меньше числа n, в единственной строке.

Примеры

Оценивание

40% — n ≤ $10^5$

60% — n ≤ $10^{18}$