Description

An integer $N > 1$ is given. We say that an integer $d > 1$ is a divisor of $N$ with multiplicity $k > 0$ ($k$ is integer) if $d^k \mid N$ and $d^{k+1}$ does not divide $N$. For example, the number $N = 18 = 16 \cdot 3$ has the following divisors: 2 with multiplicity 4, 3 with multiplicity 1, 4 with multiplicity 2, 6 with multiplicity 1, and so on.

We say that a number $d$ is a divine divisor of the number $N$ if $d$ is a divisor of $N$ with multiplicity $k$ and $N$ has no divisors with multiplicities greater than $k$. For example, the sole divine divisor of 48 is 2 (with multiplicity 4), and the divine divisors of 6 are: 2, 3 and 6 (each with multiplicity 1).

Your task is to determine the multiplicity of divine divisors of $N$ and the number of its divine divisors.

Input

Output

Example

For the input data:

3
4 3 4

the correct result is:

4
1

whereas for the input:

1
6

the correct result is:

1
3

Grading

Should your program print out the correct multiplicity $k$ of a divine divisor of $N$, but fail to print in the second line the correct number $D$ of divine divisors of $N$ (or fail to print that number at all), it will be awarded 50% of the score for that particular test, scaled accordingly if it exceeds half the time limit.

Input Format

The number $N$ is given on the standard input, though in a somewhat unusual way. The first line holds a single integer $n$ ($1 \le n \le 600$). The second line holds $n$ integers $a_i$ ($2 \le a_i \le 10^{18}$) separated by single spaces. These denote that $N = a_1 \cdot a_2 \cdot \dots \cdot a_n$.

Output Format

The first line of the standard output should hold the maximum integer $k$ such that there exists a divisor $d$ of $N$ such that $d^k \mid N$. The second line should hold a single integer $D$ that is the number of (divine) divisors of $N$ with multiplicity $k$.

3
4 3 4

4
1

1
6

1
3

Hint

Should your program print out the correct multiplicity $k$ of a divine divisor of $N$, but fail to print in the second line the correct number $D$ of divine divisors of $N$ (or fail to print that number at all), it will be awarded 50% of the score for that particular test.

Task author: Jakub Radoszewski.