Задание

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

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

2. Далее эта запись обрабатывается по правилу:

а) если число M делится на 3, то к этой записи дописываются три последние двоичные цифры;

б) если число M на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.

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

3. Результат переводится в десятичную систему и выводится на экран.

Пример. Для исходного числа 1210 = 11002 результатом является число 11001002 = 10010,

а для исходного числа 410= 1002 это число 100112 = 1910.

Какое наименьшее число S, которое больше 15110, может являться результатом работы данного алгоритма. В ответе запишите это число в десятичной системе счисления.