tai

Un număr este prim dacă are exact doi divizori naturali. Prin tăierea unui număr în $p$ părți înțelegem împărțirea acestuia în $p$ numere, fiecare de cel puțin o cifră, astfel încât prin alipirea numerelor obținute de la stânga la dreapta obținem numărul inițial.

De exemplu, dacă împărțim numărul $12045$ în două părți avem patru variante de tăiere obținându-se numerele: $1$ și $2045$; $12$ și $045$; $120$ și $45$; $1204$ și $5$. Dacă îl împărțim în trei părți avem șase variante de tăiere obținându-se numerele $1$, $2$ și $045$; $1$, $20$ și $45$; $1$, $204$ și $5$; $12$, $0$ și $45$; $12$, $04$ și $5$; $120$, $4$ și $5$.

Cerință

Se consideră un șir format din $N$ numere naturale.

1. Determinați cel mai mare număr prim din șirul celor $N$ numere.
2. Determinați cel mai mare număr prim dintre cele obținute prin tăierea în două părți a fiecărui număr din șirul celor $N$.
3. Determinați cel mai mare număr prim dintre cele obținute prin tăierea în trei părți a fiecărui număr din șirul celor $N$.

Date de intrare

Pe prima linie a fișierului tai.in se găsește numărul $C$ care poate avea doar valorile $1$, $2$ sau $3$ și reprezintă cerința care urmează a fi rezolvată. Pe a doua linie se găsește $N$, cu semnificația din enunț, iar pe a treia linie se găsește șirul celor $N$ numere naturale despărțite prin câte un spațiu.

Date de ieșire

În fișierul de ieșire tai.out pe prima linie se va afișa un număr natural reprezentând răspunsul la cerința specificată.

Restricții și precizări

• $1 \leq N \leq 100$;
• $0 \leq$ orice număr din șir $\leq 10^9$;
• Pentru cerințele $2$ și $3$ se garantează că pentru toate numerele din șir se poate efectua tăierea
• Pentru cerința $1$ dacă șirul nu conține numere prime se va afișa $0$
• Pentru cerințele $2$ și $3$ dacă în urma tăierilor nu se obține niciun număr prim, se va afișa $0$
• Pentru rezolvarea fiecărei cerințe se obțin $30$ de puncte.

Exemplul 1

tai.in

1
5
2 13 21 17 1

tai.out

17

Explicație

Numere prime din șir sunt $2$, $13$ și $17$, iar maximul este $17$.

Exemplul 2

tai.in

2
3
23 196 27

tai.out

19

Explicație

Din $23$ se obțin două numere $2$ și $3$, din $196$ se pot obține numerele $1$ și $96$ sau $19$ și $6$, iar din $27$ se obțin numerele $2$ și $7$. Cel mai mare număr prim care se poate obține este $19$.

Exemplul 3

tai.in

3
3
1234 17119 5678

tai.out

71

Explicație

Din numărul $1234$ se pot obține numerele: $1$, $2$, $34$ sau $1$, $23$, $4$ sau $12$, $3$, $4$. Din numărul 17119 se pot obține numerele: $1$, $7$ și $119$ sau $1$, $71$ și $19$ sau $1$, $711$ și $9$ sau $17$, $1$ și $19$ sau $17$, $11$ și $9$.

Din numărul $5678$ se pot obține numerele: $5$, $6$ și $78$ sau $5$, $67$ și $8$ sau $56$, $7$ și $8$. Cel mai mare număr prim care se poate obține este $71$.