Unu Doi

Se dă operația $\bar{x}:\{1,2\}\to \{1,2\}$ astfel încât $\bar{1}=2$ și $\bar{2}=1$. Operația se poate extinde asupra oricărei secvențe formate cu cifre de 1 și 2, de exemplu $\overline{121121212}=212212121$.

Se consideră șirul infinit s format cu cifre de 1 și 2, generat incremental prin extindere, după următoarea regulă de concatenare:

• $s_1=1221$
• $s_2=1221211221121221$
• …
• $s_{k+1}=s_k\overline{s_k}\overline{s_k}{s}_k$, pentru orice număr natural k.

Cerința

Dându-se un număr natural n, să se determine a n-a cifră a șirului infinit s.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran a n-a cifră a șirului s.

Restricții și precizări

• $1\le n\le {10}^8$

Exemplu:

Intrare

11

Ieșire

1

Intrare

20

Ieșire

2