Se consideră operația : {1; 2} → {1; 2}, astfel încât 1 = 2, 2 = 1. Operația se extinde asupra oricărei secvențe formate cu cifre de 1 și 2, de exemplu 1211212121 =2122121212.
Se consideră șirul infinit s format cu cifre de 1 și 2, generat incremental prin extindere după următoarea regulă de concatenare:
s1 = 1221, s2 = 1221211221121221, … , sk+1 = sk sk sk sk, …, pentru orice număr natural nenul k.

Cerința

Să se scrie un program care pentru un n număr natural nenul cunoscut determină și afișează a n-a cifră a șirului s, astfel încât numărul de pași ai programului să fie proporțional cu log2(n) (complexitate timp logaritmică în funcție de n).

Date de intrare

Fișierul de intrare extindere.in conține pe prima linie numărul natural nenul n.

Date de ieșire

Fișierul de ieșire extindere.out va conține pe prima linie numărul c care reprezintă a n-a cifră a șirului format după regula precizată mai sus.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000

Exemplu:

extindere.in

18

extindere.out

1

Explicație

Pentru a afla cifra aflată pe poziția n=18 trebuie efectuate 3 pași de extindere.
Șirul generat este 1221211221121221 2112122112212112 2112122112212112 1221211221121221.
Cifra aflată pe poziția 18 este 1.