Maximize GCD via Prime Factor Transfers

You are given a sequence of n positive integers. You are allowed to perform the following operation any number of times:

Choose two numbers from the sequence, call them \(A\) and \(B\). Then choose a prime number \(X\) which divides \(A\). Replace \(A\) with \(\frac{A}{X}\) and \(B\) with \(B \times X\).

The score of the sequence is defined as the greatest common divisor (GCD) of all n numbers. Your task is to determine the maximum possible score obtainable by performing these operations, and among all ways to achieve that maximum score, compute the minimum number of operations required.

Hint: For each prime \(p\) that appears in the prime factorization of the numbers, let \(S_p\) be the total exponent of \(p\) in the entire sequence. In the optimal arrangement, each number will have at least \(\left\lfloor \frac{S_p}{n} \right\rfloor\) occurrences of \(p\). The maximum possible GCD is \(\prod_{p} p^{\lfloor \frac{S_p}{n} \rfloor}\), and the minimum number of operations is the sum over all primes of the total deficit (i.e. for each number, if it has fewer than \(\lfloor \frac{S_p}{n} \rfloor\) occurrences of \(p\), add the difference).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of integers in the sequence.

The second line contains n space-separated positive integers. Each integer will be at most 10⁹.

outputFormat

Output two space-separated integers: the maximum possible GCD of the sequence after performing the operations, and the minimum number of operations required to achieve that GCD.

sample

3
2 4 8

4 1