Автомат с битом чётности

Автомат получает на вход натуральное число $N$ и строит новое число $R$ по следующим правилам. 1. Строится двоичная запись числа $N$. 2. Справа дописывается бит чётности: 0, если в записи чётное число единиц, и 1, если нечётное. 3. Над полученной записью повторяется действие пункта 2. Полученная запись — двоичная запись числа $R$. Укажите наименьшее число $N$, для которого результат $R$ больше 150.

Тренировочный вариант в формате КИМ ЕГЭ. Составлен по структуре и типам заданий ЕГЭ.