TÜBİTAK adasında N tane öğrenci yaşamaktadır. Artık soru çözmekten sıkılan öğrenciler bir oyun oynamaya karar verirler. Öğrenciler bir çember etrafına dizilip her koltuğa 1’den başlayarak numara verilir (saat yönünde). Oyun 1. sırada oturan kişinin ıspanak yemeye gönderilmesiyle başlar.

Ondan sonraki ıspanak yemeye gönderilecek kişi ise son gönderilen kişiden iki sonraki öğrencidir (saat yönünde ve ıspanak yemeye gönderilen öğrenciler sayılmıyor). Bahadır ıspanaktan nefret ediyor, o yüzden ıspanak yemek zorunda kalmamak için kaçıncı sıradaki koltuğa oturması gerektiğini size soruyor.

Girdi Biçimi

İlk satırda bir adet tam sayı N verilecektir. Bu sayı adadaki öğrenci sayısıdır.

Çıktı Biçimi

Oyun başında Buğdayın ıspanak yemek zorunda kalmaması için oturması gereken koltuğun numarası.

Sınırlar

• 1 ≤ N ≤ 10⁹

Alt Görevler

• Alt Görev 1 (10 puan): 1 ≤ N ≤ 10
• Alt Görev 2 (20 puan): 1 ≤ N ≤ 100
• Alt Görev 3 (40 puan): 1 ≤ N ≤ 100000
• Alt Görev 4 (30 puan): Hiçbir ek kısıtlama yok.

Örnek 1

Girdi:

4

Çıktı:

4

Açıklama

İlk turda 1. koltukta oturan kişi ıspanak yemeye gönderiliyor. Ardından ondan iki sonraki yani 3. koltukta oturan ıspanak yemeye gönderiliyor. Geriye 4 numaralı koltuktaki öğrenci ve 2 numaralı koltuktaki öğrenci kalıyor. En son turda da 2 numaralı koltuktaki öğrenci ıspanak yemeye gönderiliyor. Sonuç olarak eğer Bahadır oyun başlamadan 4 numaralı koltuğa oturursa ıspanak yemek zorunda kalmaz.

Örnek 2

Girdi:

11

Çıktı:

6

Açıklama

İlk turda 1. koltuktaki öğrenci ıspanak yemeye gönderiliyor. Sonraki turda 3. koltuktaki, ondan sonraki turda 5. koltuktaki, ondan sonraki turda 7. koltuktaki, sonraki turda 9. koltuktaki, sonraki turda 11. koltuktaki, sonraki turda 4. koltuktaki, sonraki turda 8. koltuktaki öğrenci, sonraki turda 2. koltuktaki, en son turda da 10. koltuktaki öğrenci ıspanak yemek zorunda kalıyor. Bahadır 6 numaralı koltuğa oturmalı ki ıspanak yemek zorunda kalmasın.