Манай найзууд энэ жил Нвобск-д ямар их даарч байгааг чи төсөөлөх ч үгүй байх даа! Тэдний хоёр нь дулаацахын тулд дараах тоглоомыг тоглов. Анх $q$ бүхэл тоог агуулсан цаас байсан. Тухайн тоглогч өөрийн нүүх ээлж дээр сүүлчийн бичигдсэн бүхэл тооны тодорхой хуваагч (жишээ нь, $12$-ын тодорхой хуваагчид нь $1$, $12$) биш тоог бичнэ. Тэгээд тэрээр тийм удаа зочид буудалыг тойрч гүйнэ. Тооны тодорхой хуваагч гэж уг тоо болон $1$-г хэлдэг гэдгийг сануулъя

Хамгийн эхэнд нүүж чадахгүй болсон тоглогч ялж нөгөө тоглогчоо гүйх зуур орон дотроо $3$ давхар хөнжилөө нөмрөн хэвтэнэ. Хэрэв хоёр тоглогч хамгийн сайн стратегиар тоглодог гэж үзвэл хэн ялахыг ол. Хэрвээ эхний тоглогч ялах бол эхний нүүдлийг нь хэвлэ.

Оролт

Эхний мөрөнд $q$ тоо ($1 ≤ q ≤ 10^{13}$) өгөгдөнө.

Гаралт

Эхний мөрөнд ялах тоглогийн дугаар ($1$ эсвэл $2$). Хэрвээ эхний тоглогч ялах бол хоёрдугаар мөрөнд түүний эхний нүүдлийг хэвлэнэ (эхний нүүдлээ ч хийх боломжгүй бол $0$-г хэвлэ). Хэрвээ олон шийдтэй бол алыг нь ч хэвлэсэн болно.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Number $6$ has only two non-trivial divisors: $2$ and $3$. It is impossible to make a move after the numbers $2$ and $3$ are written, so both of them are winning, thus, number $6$ is the losing number. A player can make a move and write number $6$ after number $30$; $6$, as we know, is a losing number. Thus, this move will bring us the victory.