e-olymp
Задачи

Симметрия

Симметрия

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

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.

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

Входные данные

В первой строке целое число k (1k109) – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

Выходные данные

В первой строке одно целое число – номер цвета заданной бусинки.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
10
Выходные данные
2