Задача E. Палиндром здесь, палиндром там... ≡

Условие

Сегодня на уроке математики ребята выбирали задания на лето - проекты, которые они будут реализовывать в свободное время. Тимофей опоздал на урок и ему досталась отвергнутая всеми и совершенно на первый взгляд скучная тема "числа-палиндромы".

Анализируя числа, Тимофей заметил, что некоторые из них сохраняют свою "палиндромность" и в двоичной системе счисления. Теперь он хочет совершить настоящий переворот в математике и вывести формулу, связывающую порядковый номер такого числа и само число.

Мы не требуем от вас такого же подвига, просто решите эту задачу!

Напомним, что число является палиндромом, если оно одинаково читается в обоих направлениях. Например, в десятичной системе счисления числа 1, 33, 1001 - палиндромы, а 13, 20 или 1024 - нет. Аналогично, в двоичной системе счисления, числа 1, 100001, 10111101 - палиндромы, а 110, 1010 - нет.

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

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

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

Выведете одно натуральное число - соответствующий палиндром (в десятичной системе счисления).

Ограничения

1 ≤ n ≤ 40

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

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

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

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

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

Комментарий к первому примеру: Первое натуральное число, запись которого является палиндромом и в десятичной, и в двоичной системах счисления, равно 1. Приведем ряд из семи первых чисел, обладающих таким же свойством: 1 (1₂), 3 (11₂), 5 (101₂), 7 (111₂), 9 (1001₂), 33 (100001₂), 99 (10111101₂).

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

7

99