Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.
Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте.
Входные данные
Дано натурально число число N (1 ≤ N ≤ 1018).
Выходные данные
Выведите число, которое стоит на
k-ом месте в последовательности.