A. Ял эсвэл хөлд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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

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

Оролт

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

Гаралт

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

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

Орчуулсан: Баттулга

Жишээ тэстүүд

Оролт
6
Гаралт
2
Оролт
30
Гаралт
1
6
Оролт
1
Гаралт
1
0

Тэмдэглэл

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.

Сэтгэгдлүүдийг ачааллаж байна...