După ce în timpul vacanței, Alex a vizionat filmul The Good, The Bad and The Ugly, el a descoperit o proprietate interesantă a numerelor naturale, aceea de a fi număr bun sau număr rău.

Pentru a determina dacă un număr X este bun sau rău, Alex procedează astfel:

• Determină lista divizorilor naturali ai numărului X;
• Apoi, el calculează suma pătratelor acestor divizori;
• În final, însumează cifrele sumei rezultate și notează acest rezultat cu S;
• Dacă S este par, atunci Alex va ști că numărul dat este bun;
• Dacă S este impar, atunci X va fi rău.

Pentru a vă ajuta să înțelegeți mai bine proprietatea, Alex va afla dacă numărul 34 este bun sau rău.

• 34 are ca divizori pe 1, 2, 17, 34
• Suma pătratelor acestor divizori este 12 + 22 + 172 + 342 = 1 + 4 + 289 + 1156 = 1450
• S = 1 + 4 + 5 + 0 = 10 este par, deci numărul este bun

Alex primește cadou un șir A cu N numere naturale. Spunem că o secvență a șirului A este rea, dacă și numai dacă ea este alcătuită doar din numere rele.

Acum, prietenii lui care nu au vizionat filmul îi pun mai multe întrebări.

Cerința

1. Mihai vrea să afle care este cel mai mare număr prim din șirul dat.
2. Răzvan se întreabă câte numere bune sunt în vectorul A.
3. Adelin cere găsirea celei mai lungi secvențe rele din șir.

Scrieți un program care să răspundă la aceste întrebări. Dacă reușiți să răspundeți corect la toate, Alex vă va recompensa cu 100 de puncte și un bilet la film!

Date de intrare

Fișierul de intrare bunrau.in se va afla un număr natural C, reprezentând cerința la care trebuie sa răspundeți. Pe linia a doua se află numărul N, iar pe cea de-a treia cele N elemente ale șirului A.

Date de ieșire

Fișierul de ieșire bunrau.out va conține un singur număr reprezentând, în funcție de cerință, răspunsul.

Restricții și precizări

• C ≤ 3
• N ≤ 1 000 000
• A[i] ≤ 1 000 000, pentru oricare i ≤ N
• Se garantează că există cel puțin un număr prim în șir
• Pentru C = 1, se obțin 30 de puncte
• Pentru C = 2, se obțin 50 de puncte
• Pentru C = 3, se obțin 20 de puncte
• O secvență a unui șir de numere este un subșir al acestuia, format din elemente învecinate.

Exemplul 1:

bunrau.in

1
5
2 21 5 6 13

bunrau.out

13

Explicație

C = 1, deci se rezolvă prima cerință. 2, 13 și 5 sunt singurele numere prime din șir. Dintre acestea, 13 este maximul.

Exemplul 2:

bunrau.in

2
6
9 27 12 17 3 34

bunrau.out

3

Explicație

C = 2, deci se rezolvă a doua cerință. 9, 27 și 34 sunt toate numerele bune din șirul dat. Astfel, răspunsul va fi 3.

Exemplul 3:

bunrau.in

3
8
11 7 13 33 17 14 26 34

bunrau.out

4

Explicație

C = 3, deci se rezolvă a treia cerință. Numerele rele sunt : 11, 7, 33, 17, 14, 26. Observăm că există 2 secvențe rele, una de lungime 2, alta de lungime 4.