Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. К десятичной записи справа дописывается последняя цифра числа N.
2. Получившееся число переводится в двоичное представление.
3. К двоичной записи этого числа справа дописывается бит четности, единица, если количество единиц в двоичной записи нечетно, 0 — если четно.
4. Полученное в результате этих операций число переводится в десятичную систему счисления.
Пример.
Дано число 13.
1310 -> 13310 -> 100001012 -> 1000010112 -> 26710
Укажите минимальное число N, после обработки которого получится число, превышающее 413.