Жууху өөрийн маш том алимний модноос $n$ алим хураагаад бүх алимаа $1$-ээс $n$ хүртэл дугаарлав. Одоо тэр алимны дэлгүүрт алимаа зарна.

Жууху алимаа бүлэг болгон савлаад дараа нь зарахаар болов. Бүлэг бүр хоёр багц алимтай мөн багцууд нь нэгээс их хамгийн их ерөнхий хуваагчтай байх ёстой. Мэдээж хэрэг алим бүр хамгийн хамгийн ихдээ нэг бүлэгт орно.

Жууху бүлгүүдийн хамгийн их боломжит тоог яаж олох талаар бодож байна. Түүнд туслаарай.

Оролт

Нийт алимны тоо болох $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоог оруулна.

Гаралт

Эхний мөр нь $m$ бүхэл тоо байх ба энэ нь бүлгүүддээ авч болох хамгийн их утгийг илэрхийлнэ. Дараагийн $m$ мөр бүр нь хоёр бүхэл тооноос(одоогийн бүлэг дэх алимны тоо) бүрдэнэ.

Хэрэв нөхцөлийг хангасан хэд хэдэн хариулт байгаа бол бүгдийг нь хэвлэнэ.