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 • 2 • 3 • 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ța

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 de ieșire geologie.out trebuie să conțină pe prima linie numărul maxim cerut.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000
• 2 ≤ A[i] ≤ 1.000.000, pentru orice i=1..n
• Pentru 17 puncte, A[i] este prim, pentru orice i=1..n
• Pentru 24 de puncte, N ≤ 1000
• Pentru 36 de puncte, A[i] ≤ 50.000
• Pentru 23 de puncte, nu există alte restricții
• Datorită dimensiunilor mari, nu au putut fi adăugate toate testele

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 2 3 5 11 7 3
obținând astfel o subsecvență de 3 stalactite.
A se observa că subsecvența
3 2 3 5 11 7 3
conține de asemenea numere prime consecutive, doar că acestea nu apar în ordine strict crescătoare