Description

One day, she wrote down a sequence of $n$ numbers on a piece of paper, and told Mirko that he could perform the following operation any number of times:

• Choose two numbers in the sequence (let us call them $A, B$), then choose a prime number $X$ that divides $A$. After that, Mirko erases $A$ and writes $\frac AX$ in its original position, and erases $B$ and writes $B\times X$ in its original position.

Mirko wants to get the maximum score, because then he can get candies from his great-grandmother. The score of a sequence containing $n$ numbers is the greatest common divisor of these $n$ numbers.

Mirko is not good at this, but he really wants the candies, so he came to you. You should write a program to compute the maximum possible score, and also the minimum number of operations needed while still achieving this maximum score.

Input Format

The input consists of two lines.

The first line contains an integer $n$, the number of elements in the sequence.
The second line contains $n$ integers, describing the sequence Katica gave to Mirko.

Output Format

Output one line with two integers. The first integer is the maximum score Mirko can obtain, and the second integer is the minimum number of operations needed to obtain the maximum score.

3
4 4 1

2 1

3
8 24 9

12 3

5
4 5 6 7 8

2 2

Hint

[Sample 1 Explanation]

For sample $1$, Mirko can choose the two numbers $4$ and $1$ in the sequence, and choose the only prime factor $2$ of $4$. Then Mirko erases $4$ and $1$, and writes $2$ in both of their original positions. The score of this sequence is $2$. It can be proven that this achieves the maximum possible score, and the number of operations is minimal under this condition.

[Constraints]

For all testdata, $1\leqslant n\leqslant 100$, and each element in the sequence is at most $10^6$.

[Source]

This problem comes from COCI 2009-2010 CONTEST 4 T3 IKS. Using the original testdata settings, the full score is $70$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5