Unu Doi

Se dă operația \( \overline{x} : \left\{ 1,2 \right\} \rightarrow \left\{ 1,2 \right\}\) astfel încât \( \overline{1}=2 \) și \( \overline{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 \leq n \leq 10^8 \)

Exemplu:

Intrare

11

Ieșire

1

Intrare

20

Ieșire

2