Брюс недавно получил работу в NEERC (Numeric Expression Engineering & Research Center), где изучают и строят много различных любопытных чисел. Его первым заданием стало исследование двудесятичных чисел.

Натуральное число называется двудесятичным, если его десятичное представление является суффиксом его двоичного представления; и двоичное и десятичное представление рассматривается без ведущих нулей. Например, 1010 = 10102, так что 10 двудесятичное число. Числа 101010 = 11111100102 и 4210 = 1010102 не являются двудесятичными.

Сначала Брюс хочет создать список двудесятичных чисел. Помогите ему найти n-ое наименьшее двудесятичное число.

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

Одно целое число n (1 ≤ n ≤ 10 000).

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

Вывести одно число - n-ое наименьшее двудесятичное число в десятичном представлении.