Задание 5 ЕГЭ, информатика: Посимвольное двоичное преобразование

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

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

2.  В конец записи (справа) дописывается вторая справа цифра двоичной записи.

3.  В конец записи (справа) дописывается вторая слева цифра двоичной записи.

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

Пример. Дано число N  =  13. Алгоритм работает следующим образом:

1.  Двоичная запись числа N: 1101.

2.  Вторая справа цифра 0, новая запись: 11010.

3.  Вторая слева цифра 1, новая запись: 110101.

4.  Результат работы алгоритма R  =  53.

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