Se consideră un șir de n numere naturale nenule a = (a[1], a[2], ..., a[n]). Două numere situate pe poziții consecutive în șir (a[i] și a[i+1], unde 1 ≤ 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:

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

Cerința

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 și precizări

• 1 ≤ n ≤ 100.000
• 2 ≤ a[i] ≤ 2.000.000.000, pentru orice 1 ≤ i ≤ 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] < ... < d[k]) și f = (f[1] < f[2] < ... < 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 ≤ j < i și (d[i] < f[i] sau i = k + 1).
• Pentru 15 puncte, C = 1, 1 ≤ n ≤ 1000 și numerele din șir sunt ≤ 10.000.
• Pentru 15 puncte, C = 1, 10.000 ≤ n ≤ 100.000 și numerele din șir sunt ≤ 10.000.
• Pentru 10 puncte, C = 1, 1 ≤ n ≤ 1000 și numerele din șir sunt ≤ 2.000.000.000.
• Pentru 30 puncte, C = 1, 10.000 ≤ n ≤ 100.000 și numerele din șir sunt ≤ 2.000.000.000.
• Pentru 12 puncte, C = 2 și rezultatul va fi un număr de maximum 18 cifre.
• Pentru 18 puncte, C = 2 și rezultatul va fi un număr cu maximum 1500 cifre.

Exemplul 1:

fuziune.in

1
8
30
18
997
121
625
5
55
101

fuziune.out

4

Explicație

C=1. Numerele 30 = 2 • 3 • 5 și 18 = 2 • 3^2 vor fuziona și se obține valoarea 90 = 2 • 3^2 • 5. Numerele 625, 5 și 55 vor fuziona de asemenea, apoi rezultatul va fuziona cu 121 și se obține valoarea 75625 = 5^4 • 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 • 3^2
25 = 5^2
cf(b) = 2 • 3 • 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 • 3^2 • 5
97
75625 = 5^4 • 11^2
10403 = 101 • 103
cf(b) = 2 • 3 • 5 • 11 • 97 • 101 = 3233010.