Sequence 011212201220200112… is constructed as follows: first 0 is written, then the following action is repeated: the already written part is attributed to the right, replacing 0 with 1, 1 with 2, 2 with 0, etc.
It is required to write a program that, given a natural number N, determines what number is in the Nth position.
Input
Given a natural number number N (1 ≤ N ≤ 1018).
Output
Print the number that is at the
kth place in the sequence.