Symmetry (RU)
Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:
1) при длине ряда рисунка равной 1 использовала бусинку первого цвета;
2) при длине ряда рисунка равной 3 использовала бусинки двух цветов: 1 2 1;
3) при необходимости добавления в рисунок еще одного цвета строился ряд: 1 2 1 3 1 2 1 и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1.
Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.
Input
В первой строке целое число k (1 ≤ k ≤ 10^9) – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.
Output
В первой строке одно целое число – номер цвета заданной бусинки.