geologie

Geologul George a descoperit recent în zona Iașiului o peșteră foarte frumoasă, ideală pentru studierea stalactitelor. În peșteră se află $N$ stalactite, așezate în linie dreaptă. După săptămâni de muncă și analizare temeinică a peșterii, George a descoperit că fiecare stalactită este formată din straturi de depuneri cu diverse compoziții chimice.

Pentru a economisi timp, geologul a inventat un sistem prin care să noteze structura fiecărei stalactite. El a asociat fiecărui tip de strat diferit câte un număr prim, astfel încât, dacă două straturi au aceeași compoziție chimică, ele au asociate același număr și a calculat valoarea stalactitei, ca produs al numerelor prime ale straturilor ei.

Astfel, dacă are o stalactită cu $4$ straturi, cărora le-a asociat numerele prime $2$, $11$, $2$, $3$, atunci stalactita respectivă va avea valoarea $132 = 2 \cdot 2 \cdot 3 \cdot 11$.

George a obținut șirul $A$, de $N$ numere, reprezentând șirul valorilor stalactitelor, în ordinea în care ele apar în peșteră.

Pentru a-și finanța mai departe cercetările, George i-a invitat pe membrii comisiei științifice a Muzeului de Mineralogie şi Petrografie „Grigore Cobălcescu” din Iași să viziteze peștera. Pentru a-i impresiona, el plănuiește să aleagă o subsecvență de stalactite, aflate pe poziții consecutive în peșteră, pe care să le curețe, eliminând eventual unele straturi, astfel încât pentru fiecare stalactită să rămână exact un strat din componența acesteia (deci un singur număr prim), iar subsecvența obținută să fie formată numai din numere prime consecutive, în ordine strict crescătoare (gusturile matematice ale lui George…). Spunem că două numere prime $x$ și $y$ sunt consecutive dacă nu există niciun alt număr prim $z$ cu $x < z < y$.

Cerință

Aflați numărul maxim de stalactite care formează o subsecvență obținută prin curățare, care să fie pe gustul lui George.

Date de intrare

Pe prima linie a fișierului geologie.in se află numărul natural $N$, cu semnificația din enunț, iar pe a doua linie se află $N$ numere naturale, reprezentând termenii șirului $A$, al valorilor stalactitelor în ordinea din peșteră.

Date de ieșire

Fișierul geologie.out trebuie să conțină pe prima linie numărul maxim cerut.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $2 \leq A_i \leq 1 \ 000 \ 000$

Exemplu

geologie.in

7
3 4 6 10 11 14 21

geologie.out

3

Explicație

$A_1 = 3$ poate fi curățat, astfel încât să rămână $3$
$A_2 = 4$ poate fi curățat, astfel încât să rămână $2$
$A_3 = 6$ poate fi curățat, astfel încât să rămână $2$ sau cu $3$
$A_4 = 10$ poate fi curățat, astfel încât să rămână $2$ sau $5$
$A_5 = 11$ poate fi curățat, astfel încât să rămână $11$
$A_6 = 14$ poate fi curățat, astfel încât să rămână $2$ sau $7$
$A_7 = 21$ poate fi curățat, astfel încât să rămână $3$ sau $7$

Pentru soluția optimă $A$ poate fi modificat în felul următor: $3 \ \textbf{2 3 5} \ 11 \ 7 \ 3$, obținând astfel o subsecvență de $3$ stalactite.

A se observa că subsecvența $3 \ \textbf{2 3 5 11 7} \ 3$ conține de asemenea numere prime consecutive, doar că acestea nu apar în ordine strict crescătoare.