Для распределения подарков среди детей, Дед Мороз для каждого ребенка рассчитывает рейтинг. Первичный рейтинг N - количество добрых дел, сделанных за год. А для распределения подарков необходим результирующий рейтинг R, который строится следующим образом:
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 8, то к этой записи дописываются две последние двоичные цифры,
б) если число N на 8 не делится, то остаток от деления на 8 умножается на 2, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого результирующего рейтинга R.
3. Результат переводится в десятичную систему.
Известно, что если у ребенка результирующий рейтинг R превышает 3000, то Дед Мороз дарит ему суперподарок. Какое наименьшее количество добрых дел необходимо за год сделать ребенку, чтобы получить суперподарок?
В ответе запишите только число.