Симметрия#165
Предприимчивая и искусная мастерица решила заработать, делая браслеты из бус. Будучи поклонницей симметрии в искусстве, она расставила бусины разных цветов (цвет обозначается положительным целым числом) по следующим правилам:
1) Для рядка длины она использовала бусину первого цвета;
2) Для рядка длины она использовала бусины двух цветов: ;
3) Если нужно было добавить еще один цвет к узору, рядок составлялся так: 1\ 2\ 1\ 3\ 1\ 2\ 1; каждый раз, в зависимости от числа использованных цветов, например, для четырёх цветов: 1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1.
Напишите программу, которая определяет цвет бусины на заданной позиции в ряду.
В первой строке содержится целое число (1 \leq k \leq 10^9) — позиция бусины, цвет которой необходимо определить. Позиции бусин нумеруются с единицы.
Выведите одно целое число — номер цвета указанной бусины.
Example 1