PROGRAMING PROBLEMS

Хүслэн, Төгөлдөр хоёр математикийн хичээлдээ сонирхолтой бөгөөд төрөл бүрийн бодлого болон тоглоомоор бие биетэйгээ өрсөлддөг. Энэ удаад тэд N ширхэг жижиг чулууг овоолон, дараах дүрмийг баримтлан тоглов. 

1. Тоглогчид ээлжлэн овоолсон чулуунаас тодорхой тооны чулууг авна. Тухайлбал эхлээд Хүслэн тоглоно, дараа нь Төгөлдөр, дараа нь дахин Хүслэн, дараа нь Төгөлдөр гэх мэт. 

2. Хүслэн эхний үйлдэл хийхдээ овоолсон чулуунаас хэдэн ч ширхэг чулуу (1-ээс N-ийн хооронд) авч болно. 

3. Дараагийн ээлж бүрд тоглогч дор хаяж 1 чулуу авах ёстой бөгөөд хамгийн ихдээ өмнөх ээлжийн тоглолтоор нөгөө тоглогчийн авсан чулуунаас хоёр дахин их хэмжээгээр авахыг зөвшөөрнө. Мэдээж овоолсон чулууны үлдсэн хэмжээнээс илүү чулуу авч болохгүй. 

4. Хамгийн сүүлд чулуу авсан тоглогч ялагч болно. Хүслэн, Төгөлдөр хоёр хоёулаа оновчтой тоглодог (хэрэв нэг тоглогч нөгөөгөө хожих боломжтой бол тэр тоглогч хожих болно). Эхний тоглогч (Хүслэн) хожихын тулд анх эхлээд авч болох хамгийн цөөн чулууны тоог олох программ бичнэ үү. Ингэснээр эхний тоглогч тоглолтод хожих нь баталгаатай болно.

Оролт

Тоглоомын эхэнд байх ёстой овоолсон чулууны тоо болох N (2 <= N <= 10^15) эерэг бүхэл тоо нэг мөрөнд өгөгдөнө.

Гаралт

Эхний тоглогч хожихын тулд эхлээд авах ёстой хамгийн цөөн чулууны тоог нэг мөрөнд гаргаарай.

Жишээ

Оролт1

4

Гаралт1

1

Оролт2

7

Гаралт2

2

Оролт3

8

Гаралт3

8

Эхний жишээний тайлбар:

Хүслэнд 4 сонголт бий: Овоолгоос 1, 2, 3, 4 чулууг авч болно. Хэрэв тэр 4 чулууг бүгдийг нь авбал тэр шууд хожих болно, гэхдээ энэ нь хамгийн цөөн байх шийдэл биш.

Үлдсэн хувилбаруудыг шалгах хэрэгтэй. Хэрэв Хүслэн ганцхан чулуу авбал Төгөлдөр 3 чулуунаас хамгийн ихдээ 2-ыг л авч болно, бүх чулууг авч чадахгүй, харин Хүслэн дараагийн ээлжид үлдсэн бүх чулууг авч хожих болно. Иймээс энэхүү тестийн хамгийн цөөн байх шийдэл нь 1 байна.