Predict the Number

Programming challenge descriptlon:

The example sequence $011212201220200112...$ s constructed as follows:

$1.$ The first element in the sequence is $0.$

$2.$ For each iteration, repeat the following action: take a copy of the entire current sequence, replace $0$ with $1,1$ with $2,$and $2$ with $0,$ and place it at the end of the current sequence. E$.$g$.$

$0010012011201121220....$

Create an algorithm which determines what number is at the Nth position in the sequence $($using $0-$based indexing$).$

Input:

Your program should read lines from standard input. Each line contalns an integer N such that $0<=$ N $<=3000000000.$

Output:

Print out the number which is at the Nth position in the sequence.

Test$1$

Test Input

$5$

Expected Output

$2$

Test $2$

Test Input

$25684$

Expected Output

$0$

import sys

def solution$($n$)$:

# the code here

for line in sys$.$stdin:

n $=$ int$($line$.$strip$())$

print$($soluution $($n$))$