Problem Description

Mirko's great-grandmother Katica, a passionate mathematician, loves to torment her great-grandson with mathematical games.

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

• Select two numbers from the sequence (let's call them $A$ and $B$), and then select a prime number $X$ that divides $A$. After that, Mirko erases $A$ and writes $\frac{A}{X}$ in its place, and erases $B$ and writes $B \times X$ in its place.

Mirko wants to achieve the highest score possible because he can get candy from his great-grandmother. The score of a sequence of $n$ numbers is the greatest common divisor (GCD) of these $n$ numbers.

Mirko is not good at this but really wants the candy, so he has come to you, hoping you can write a program to calculate the maximum possible score and also the minimum number of operations needed to achieve this score.

Input Format

The input consists of two lines.

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

Output Format

Output a single line with two integers. The first integer represents the maximum score Mirko can achieve, and the second integer represents the minimum number of operations needed to achieve this maximum score.

Sample Input and Output

Sample Input #1

3
4 4 1

Sample Output #1

2 1

Sample Input #2

3
8 24 9

Sample Output #2

12 3

Sample Input #3

5
4 5 6 7 8

Sample Output #3

2 2

Notes

[Sample 1 Explanation]

For sample $1$, Mirko can choose the numbers $4$ and $1$ from the sequence and select the prime factor $2$ of $4$. Then Mirko erases $4$ and $1$ and writes $2$ in their places, resulting in a sequence with a score of $2$. It can be proven that this scheme achieves the maximum score with the minimum number of operations.

[Data Range]

For all test cases, $1 \leqslant n \leqslant 100$, and the elements in the sequence do not exceed $10^6$.

[Problem Source]

This problem is from COCI 2009-2010 CONTEST 4 T3 IKS, configured with the original problem data, with a full score of $70$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分