№5 — #5140

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему число R следующим образом. 1. Строится двоичная запись числа N. 2. Если количество единиц в двоичной записи чётно, то справа к записи дописывается 10. 3. Если количество единиц в двоичной записи нечётно, то слева к записи дописывается её последняя цифра. Полученная запись является двоичной записью числа R.

Например, для числа 6₁₀ = 110₂ получается число 11010₂ = 26₁₀, а для числа 5₁₀ = 101₂ получается число 1101₂ = 13₁₀. Укажите максимальное число N, для которого результат работы алгоритма меньше 150.