На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Каждый разряд этой записи заменяется двумя разрядами по следующему правилу:
- Если N делится нацело на 4, в конце числа (справа) дописывается сначала ноль, а затем еще один ноль,
- Если N при делении на 4 дает в остатке 1, то в конец числа (справа) дописывается сначала ноль, а затем единица,
- Если N при делении на 4 дает в остатке 2, то в конец числа (справа) дописывается сначала один, а затем ноль,
- Если N при делении на 4 дает в остатке 3, в конец числа (справа) дописывается сначала один, а затем еще одна единица.
Например, двоичная запись 1001 числа 9 будет преобразована в 100101, а двоичная запись 1100 числа 12 будет преобразована в 110000.
Полученная таким образом запись (в ней на 2 разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите максимальное число R, которое меньше 111 и может являться результатом данного алгоритма. в ответе запишите это число в десятичной системе счисления.