Хоёр сайн найз Серёжа, Гена нар тоглоом тоглож байв.

Эхлээд ширээн дээр $n$ ширхэг чулуу байв. Ѳѳрийн ээлжинд нэг хэсгийг сонгоод дурын байдлаар $a_1>a_2>...>a_k>0$ ширхэг чулуутай хэсгүүдэд хуваана. Уг хэсгүүд нь $a_1-a_2=a_2-a_3=...=a_{k-1}-a_k=1$ нѳхцлийг хангах ёстой. Мэдээж уг хуваах хэсгүүдийн тоо $k$ нь хоёроос багагүй байна.

Найзууд ээлжлэн нүүнэ. Үйлдэл хийж чадахгүй болсон тоглогч хожигдно. Серёжа хамгийн эхний үйлдлийг хийнэ. Хоёр тоглогч хамгийн зѳв тактикаар тоглоход хэн нь хожих вэ?

Оролт

Нэг мѳрѳнд бүхэл тоо $n$ ($1≤n≤10^5$) ѳгѳгднѳ.

Гаралт

Хэрвээ Серёжа хожих бол түүний хожихдоо хийх эхний үйлдэлдээ байж болох хамгийн бага хуваалтын тоо болох $k$ бүхэл тоог хэвлэ.

Хэрвээ Гена хожих бол $-1$ гэж хэвлэ.