Симетрія#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) — позиція намистини, колір якої потрібно визначити. Нумерація намистин починається з одиниці.
Виведіть одне ціле число — номер кольору вказаної намистини.
Приклад 1