Dünən Pavelin ad günü idi, həmin gün o Andrey ilə növbəti oyunu oynadı: Andrey Pavelin yaşını tapmağa çalışırdı. Andrey bilir ki, bu 1-n intervalında tam ədəddir. Andrey 1-n intervalında istənilən x ədədini deyə bilər, Pavel isə x və onun yaşının ən böyük ortaq bölənini söyləyəcək.
n = 6 qiymətində oyun üçün mümkün gedişlərdən birinə baxaq. Andrey 3 söyləyir, Pavel 3 və onun yaşının ƏBOB-nun 1-ə bərabər olduğu cavabını verir. Deməli Pavelin yaşı nə 3, nə də 6 ola bilməz, lakin 1, 2, 3 və ya 5 ola bilər. Andrey oyunu davam etdirərək 2 söyləyir, Pavel cavabın 2 olduğunu deyir. Pavelin yaşı 1-ə və ya 5-ə bərabər ola bilməz, yalnız iki variant qaldı - 2 və 4. Nəhayət Andrey 4 söyləyir, Pavel isə cavab olaraq 2 deyir. Nəticə olaraq Pavelin yaşı 2-dir, oyun bitdi.
Verilmiş misalda Andreyə 3 cəhd etmək lazım gəldi. Lakin n = 6 olduqda, Pavelə iki cəhd etmək kifayətdir. Andreyin optimal strategiyası növbəti şəkildədir: əvvəlcə 6 söyləmək lazımdır, Əgər Pavel 1 cavabını verərsə, onda 5 söyləməklə cavabın 1 və ya 5 olduğunu təyin etmək olar. Əgər Pavel 2 söyləyərsə, onda cavab 2 və ya 4 olacaqdır, onu 4 söyləməklə tapmaq olar. Əgər Pavel 3 deyərsə, onda cavab 3 olacaqdır. Əgər Pavel 6 söyləyərsə onda cavab 6-dır.
n-nin verilmiş qiymətində ən pis halda Andreyin ən az sayda etdiyi cəhtdlərin sayını tapın.
Giriş verilənlər
Giriş verilənləri n (2 ≤ n ≤ 10000) tam ədədini ehtiva edir.
Bir tam ədəd — ən pis halda Andreyə Pavelin yaşını tapması kifayət edən cəhdlərin sayı.