Задача C. Злой палиндром ≡

Условие

Злой колдун-нумеролог Тимофей готовит новое заклинание. Как и положено нумерологу, заклинание Тимофея должно содержать натуральное число. Как и положено колдовскому числу, оно должно быть палиндромом. Как и положено выбранному Тимофеем нравственно-этическому направлению, число должно быть злым.

Напомним, что число является палиндромом, если оно одинаково читается в обоих направлениях. Например, числа 1, 33, 1001 — палиндромы, а 13 или 1024 — нет.

Напомним, что число является злым, если при записи в двоичной системе счисления оно содержит чётное число единиц. Например, числа 3 (11₂ в двоичной системе счисления), 6 (110₂), 51 (110011₂) — злые, а 7 (111₂), 8 (1000₂) или 19 (10011₂) — нет.

Тимофей выписывает все подходящие для заклинания числа на листочек в возрастающем порядке. Какое число в этой последовательности окажется на n-ом месте?

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

В единственной строке записано одно натуральное число n — порядковый номер злого палиндрома.

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: 0 ≤ n ≤ 500, баллы: 30. Гарантируется, что ответ не превысит 10⁵

Подзадача 2: нет дополнительных ограничений, баллы: 70. Гарантируется, что ответ не превысит 10¹⁰

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

Комментарий к первому примеру: Первое натуральное число, являющееся одновременно палиндромом и злым числом, это 3. Оно одинаково читается в обоих направлениях, а при переводе в двоичную систему счисления имеет две (четное число) единицы в записи. Меньшие натуральные числа (1 и 2) не подходят - они хоть и палиндромы, но не являются злыми, так как содержат в своей записи в двоичной системе счисления нечетное число единиц (одну).

Комментарий ко второму примеру: Приведем ряд из десяти первых чисел на листочке Тимофея: 3, 5, 6, 9, 33, 66, 77, 99, 101, 111.

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

1

3

10

111