== include(page="template/taskheader" task_id="subsir1000") ==

Pentru a cumpăra bilete la Finala Cupei, $N$ oameni s-au aşezat la coadă. Fiecare om are locul său preferat pe care doreşte să stea, reprezentat printr-un număr strict pozitiv mai mare decât $1$ şi mai mic sau egal decât $N$. Totuşi, toată lumea ştie că nu vor fi bilete suficiente pentru toţi, aşa că organizatorii s-au hotărât să ia un subşir de oameni de lungime maximă cărora să le dea biletele rămase. Totuşi, pentru a nu stârni suspiciuni, s-a hotarât ca în acest subşir oricare două persoane consecutive trebuie să *nu* aibă numerele locurilor preferate prime între ele (în acest mod organizatorii cred că persoanele nu vor ieşi în evidenţă).
Aşadar, în schimbul unei părţi din profit în valoare de 100 de puncte, organizatorii vă cer ajutorul: trebuie să determinaţi cel mai lung subşir astfel încât oricare două elemente *consecutive* să *nu* fie prime între ele.

Pentru a cumpăra bilete la Finala Cupei, $N$ oameni s-au aşezat la coadă. Fiecare om are locul său preferat pe care doreşte să stea, reprezentat printr-un număr strict pozitiv mai mare decât $1$ şi mai mic sau egal decât $N$. Totuşi, toată lumea ştie că nu vor fi bilete suficiente pentru toţi, aşa că organizatorii s-au hotărât să ia un subşir de oameni de lungime maximă cărora să le dea biletele rămase. Totuşi, pentru a nu stârni suspiciuni, s-a hotarât ca în acest subşir oricare două persoane consecutive trebuie să aibă numerele locurilor preferate prime între ele (în acest mod organizatorii cred că persoanele vor fi împarţite cât mai uniform).
Aşadar, în schimbul unei părţi din profit în valoare de 100 de puncte, organizatorii vă cer ajutorul: trebuie să determinaţi cel mai lung subşir astfel încât oricare două elemente sa fie prime între ele.

h2. Date de intrare

h2. Restricţii

* $2 ≤ N ≤ 100 000$
* Considerând că şirul dat este $A = (a{~1~},a{~2~},...a{~N~})$, se numeşte subşir al lui $A$ un şir $B = (a{~i1~},a{~i2~},...a{~iK~})$ cu proprietatea că $1 ≤ i1 < i2 < ... < iK ≤ N$.
* Pe organizatori nu îi interesează dacă din subşir fac parte două sau mai multe persoane cu acelaşi loc preferat. Ei le dau biletele şi îi lasă pe ei să îşi rezolve problema.

* $1 ≤ N ≤ 100 000$
* Considerând că şirul dat este $A = (a{~1~},a{~2~},...a{~N~})$, se numeşte subşir al lui $A$ un şir $B = (b{~i1~},b{~i2~},...b{~iN~})$ cu proprietatea că $1 ≤ i1 < i2 < ... < iK ≤ N$.

h2. Exemplu
table(example). |_. subsir1000.in |_. subsir1000.out |

| 7
5 3 4 6 2 5 6

| 6
5 3 4 2 6 3

| 4
|
h3. Explicaţie

O soluţie posibila este: $3 6 2 6$

Vezi enunţ :)

== include(page="template/taskfooter" task_id="subsir1000") ==

5449