Автомат: остаток числа единиц, дважды

Автомат получает на вход натуральное число $N$ и преобразует его по следующему алгоритму. 1. Строится двоичная запись числа $N$. 2. Подсчитывается число единиц в записи, находится остаток $k$ от деления этого числа на 3. 3. К записи справа дописывается двухразрядная двоичная запись числа $k$ (00, 01 или 10). 4. Пункты 2 и 3 повторяются для полученной записи ещё один раз. Полученная запись — двоичная запись числа $R$. Найдите наибольшее $N$, для которого $R < 500$.

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