На вход алгоритма подаётся натуральное число \(N.\) Алгоритм строит по нему новое число \(R\) следующим образом.
1. Строится двоичная запись числа \(N.\)
2. Далее эта запись обрабатывается по следующему правилу:
а) если число \(N\) делится на \(3,\) то к этой записи дописываются три последние двоичные цифры;
б) если число \(N\) на \(3\) не делится, то остаток от деления умножается на \(3,\) переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа \(R.\)
3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа \(12_{10} = 1100_2\) результатом является число \(1100100_2 = 100_{10},\) а для исходного числа \(4_{10} = 100_2\) это число \(10011_2 = 19_{10}.\)

Какое число могло быть получено с помощью предложенного алгоритма?

• \(94_{10}=1011110_2\)
• \(30_{10}=11110_2\)
• \(42_{10}=101010_2\)
• \(90_{10}=1011010_2\)