reducere

O operaţie de reducere aplicată asupra unui șir constă în selectarea unui număr prim $p$ şi a unor elemente din șirul dat care sunt divizibile cu $p$ şi împărţirea acestora la $p$.

Asupra unui șir format din $n$ numere naturale nenule se aplică o succesiune de operaţii de reducere, până când toate elementele șirului devin egale. Valoarea finală a elementelor șirului este denumită valoare de egalitate.

Valoarea de reducere a unui șir este cea mai mare dintre valorile de egalitate care se pot obţine în urma aplicării unor operaţii de reducere asupra acestui șir.

Cerință

• Determinați valoarea de reducere pentru un șir dat.
• Determinați numărul minim de operaţii de reducere care trebuie să fie aplicate șirului dat pentru a obţine valoarea de reducere.

Date de intrare

Fişierul de intrare reducere.in conţine pe prima linie un număr natural $C$, reprezentând cerința care trebuie să fie rezolvată ($1$ sau $2$), pe a doua linie un număr natural $n$, iar pe următoarele $n$ linii câte un număr natural, reprezentând câte un element al șirului.

Date de ieșire

Fişierul de ieşire reducere.out va conţine o singură linie, pe care va fi scris numărul determinat pentru cerinţa $C$ din fișierul de intrare.

Restricții și precizări

• $2 \leq n \leq 2 \ 000$
• Elementele șirului sunt numere naturale nenule $\leq 10^{12}$.

Exemplul 1

reducere.in

1
3
10
6
12

reducere.out

2

Explicație

Operaţia de reducere $1$: împărţim prin $3$ pe $6$ şi pe $12 \Rightarrow 10, 2, 4$

Operaţia de reducere $2$: împărţim prin $5$ pe $10 \Rightarrow 2, 2, 4$

Operaţia de reducere $3$: împărţim prin $2$ pe $4 \Rightarrow 2, 2, 2$

Valoarea de reducere este $2$, aceasta fiind cea mai mare dintre valorile de egalitate posibile.

Exemplul 2

reducere.in

2
3
10
6
12

reducere.out

3