fuziune

Se consideră un șir de $n$ numere naturale nenule $a = (a_1 a_2 \dots a_n)$. Două numere situate pe poziții consecutive în șir ($a_i$ și $a_{i+1}$, unde $1 \leq i < n$) pot fuziona dacă ele au cel puțin un divizor comun strict mai mare decât $1$. În urma fuziunii ele vor fi înlocuite de cel mai mic număr care se divide cu toți divizorii lui $a_i$ și ai lui $a_{i+1}$. Operația de fuziune se poate repeta, pe noul șir obținut, până când în șir nu va exista nicio pereche de numere situate pe poziții consecutive care să poată fuziona. Să notăm cu $b$ șirul obținut după efectuarea tuturor operațiilor de fuzionare.

Numim coeficient de fuziune al șirului $b$ și îl notăm cu $cf(b)$ un număr nenul care are proprietatea că orice termen al șirului $b$ are cel puțin un divizor comun cu $cf(b)$, strict mai mare decât $1$. În plus, $cf(b)$ trebuie să respecte următoarele condiții:

1. factorii săi primi sunt distincți (de exemplu $30 = 2 \sdot 3 \sdot 5$ are doar factori primi distincți, dar $18 = 2 \sdot 3 \sdot 3$ nu are doar factori primi distincți);
2. orice factor prim al lui $cf(b)$ este factor prim pentru cel puțin un număr din șirul $b$;
3. lista factorilor primi distincți ai lui $cf(b)$ ordonată strict crescător este minimă din punct de vedere lexicografic.

Cerință

Dat fiind un șir de numere naturale nenule, scrieți un program care să rezolve următoarele două cerințe:

1. să se determine lungimea minimă a șirului $b$ obținut după efectuarea tuturor operațiilor de fuziune posibile;
2. să se determine $cf(b)$.

Date de intrare

Fișierul de intrare fuziune.in conține pe prima linie cerința $C$ care trebuie să fie rezolvată ($1$ sau $2$). Pe cea de-a doua linie se află un număr natural $n$, reprezentând numărul de valori din șir. Pe următoarele $n$ linii se află cele $n$ numere din șir, câte un număr pe o linie.

Date de ieșire

Fișierul de ieșire fuziune.out va conține o singură linie pe care va fi scris răspunsul la cerința $C$ din fișierul de intrare.

Restricții

• $1 \leq n \leq 100 \ 000$;
• $2 \leq a_i \leq 2 \sdot 10^9$, pentru orice $1 \leq i \leq n$;
• Se garantează că numărul de factori primi distincți pentru numerele din șirul $b$ (pentru cerința $1$) și pentru $cf(b)$ (pentru cerința $2$) este cel mult egal cu $250$.
• Fie $d = (d_1 < d_2 < \dots < d_k)$ și $f = (f_1 < f_2 < \dots < f_h)$ două liste de factori primi distincți ordonate strict crescător. Spunem că $d$ este mai mică din punct de vedere lexicografic decât $f$ dacă există o poziție $i$ astfel încât $d_j = f_j$, pentru orice $1 \leq j < i$ și ($d_i < f_i$ sau $i = k + 1$).

Exemplul 1

fuziune.in

1
8
30
18
997
121
625
5
55
101

fuziune.out

4

Explicații

$C = 1$.
Numerele $30 = 2 \sdot 3 \sdot 5$ și $18 = 2 \sdot 32$ vor fuziona și se obține valoarea $90 = 2 \sdot 3^2 \sdot 5$.
Numerele $625$, $5$ și $55$ vor fuziona de asemenea, apoi rezultatul va fuziona cu $121$ și se obține valoarea $75625 = 5^4 \sdot 11^2$.
În șirul rezultat vor rămâne, după efectuarea tuturor fuzionărilor $4$ numere ($90$, $997$, $75625$ și $101$).

Exemplul 2

fuziune.in

2
3
16
18
25

fuziune.out

30 

Explicație

$C = 2$.
În urma efectuării tuturor operațiilor de fuziune posibile se obține șirul:
$144 = 2^4 \sdot 3^2$
$25 = 5^2$
$cf(b) = 2 \sdot 3 \sdot 5 = 30$.

Exemplul 3

fuziune.in

2
8
30
18
97
121
625
5
55
10403

fuziune.out

3233010

Explicație

$C = 2$.
În urma efectuării tuturor operațiilor de fuziune posibile se obține șirul
$90 = 2 \sdot 3^2 \sdot 5$
$97$
$75625 = 5^4 \sdot 11^2$
$10403 = 101 \sdot 103$
$cf(b)=2 \sdot 3 \sdot 5 \sdot 11 \sdot 97 \sdot 101 = 3233010$.