Алгоритм получает на вход натуральное число 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? В ответе запишите это число в десятичной системе счисления.

• 38
• 40
• 39
• 37