*На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Если число N делится на 3, в конец двоичной записи дописывается двоичный код числа 3, иначе дописывается единица.
3. Если число, полученное после шага 2, делится на 5, в конец двоичной записи дописывается двоичный код числа 5, иначе дописывается единица.
4. Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 7₁₀ = 111₂ (не делится на 3) после шага 2 получается число 1111₂ = 15₁₀ (делится на 5), а после шага 3 – число 1111101₂ = 125₁₀. Определите наибольшее возможное значение N, для которого в результате работы алгоритма получается R < 10₆.