Жақсылық қазынаны табу ұшін ежелгi ғибадатханада басқатырғыш жұмбақты шешу қажет. Оның алдында \(n\) тастары бар есiк тұр, оны ашу үшiн тастың үстіне басу керек. рғышты шешуге тырысыңыз. Жақсылық тасты басқан кезде, ол дұрыс қадам болса, тас жанады, ал егер тастарды өзге түрмен басса, барлық жаңған тастар өшiрiледi. Барлық тастар жаңған кезде есiк ашылады.

Жақсылық басу ретiн бiлмейдi, бiрақ ол өте зерек және дұрыс әрекет етедi. Ең нашар жағдайда есiктi ашу үшiн қанша шерту саны қажет.

Енгізу

Құрамында \(n\) \((1 \le n \le 2000)\) — тастар саны бүтін сан бар.

Шығару

Ең нашар жағдайда басу санын шығарыңыз.

Мысалдар

Енгізу 1

3

Жауап 1

7

Ескертпелер

Үш таспен мысалды қарастырайық. Тастарды жандырудың дұрыс реттiлiгi: 2, 3, 1. Алдымен 1 немесе 3 тастарды бассаңыз, олар бiрден өшедi. 2-шi тасты бассаңыз, ол жанып қалады. Егер сiз 1 тасты бассаңыз, барлық тастар өшiрiледi. Бiрақ 2 тасты iске қосқаннан кейiн 3 тасты бассаңыз, екi тас жанып қалады. Есiктi ашу үшiн 1-шi тасты басу ғана қалады.