Задание

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом:

1. Строится двоичная запись числа M.

2. К этой записи дописываются справа ещё несколько разрядов по следующему правилу:

а) если M чётное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи;

6) если M нечётное, то к нему справа приписываются два нуля, а слева единица.

Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа M) является двоичной записью искомого числа S.

Пример. Запись числа 11012 будет преобразована в 11101002.

При каком наименьшем числе M в результате работы алгоритма получится S > 21510. В ответе запишите это число в десятичной системе счисления.