Задача №111589. Последовательность

Последовательность 011212201220200112... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.:

0 → 01 → 0112 → 01121220 →  ...
Составить алгоритм, который по введенному k определяет, какое число стоит на k-ом месте в последовательности.

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

Дано натуральное число k (1 ≤ k ≤ 1018).

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

Выведите число, которое стоит на k-ом месте в последовательности.

Примеры тестов

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

Сдать: для сдачи задач необходимо войти в систему