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

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 (1 ≤ k ≤ 109) - номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

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