신성한 약수

$N > 1$인 정수가 주어진다. 정수 $d > 1$에 대해, $d^k \mid N$이면서 $d^{k+1} \nmid N$을 만족하는 양의 정수 $k$가 존재할 때 "$d$는 $N$의 중복도가 $k$인 약수"라고 한다. 예를 들어 $N = 48 = 2^4 \cdot 3$의 경우 $2$는 중복도가 $4$인 약수, $3$은 중복도가 $1$인 약수, $4$는 중복도가 $2$인 약수, $6$은 중복도가 $1$인 약수이다.

$d$가 $N$의 중복도가 $k$인 약수이면서 $N$의 모든 약수 중 $k$보다 큰 중복도를 가지는 약수가 없을 때, $d$를 $N$의 신성한 약수라고 한다. 다시 말해 신성한 약수는 $N$의 모든 약수가 가지는 중복도의 최댓값을 달성하는 약수이다. 예를 들어 $48$의 신성한 약수는 $2$ (중복도 $4$) 하나뿐이고, $6$의 신성한 약수는 $2$, $3$, $6$ (각각 중복도 $1$)이다.

$N$의 모든 약수가 가지는 중복도의 최댓값 $k$와 $N$의 신성한 약수의 개수를 구하라.

$N$은 다소 특이한 방식으로 주어진다. 첫 번째 줄에는 정수 $n$ ($1 \le n \le 600$)이 주어진다. 두 번째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($2 \le a_i \le 10^{18}$)이 공백 하나로 구분되어 주어진다. 이들은 $N = a_1 \cdot a_2 \cdot \cdots \cdot a_n$을 뜻한다.

두 줄을 출력한다. 첫 번째 줄에는 $N$의 어떤 약수 $d > 1$이 $d^k \mid N$을 만족하도록 하는 가장 큰 정수 $k$를 출력한다. 두 번째 줄에는 $N$의 신성한 약수의 개수, 즉 중복도가 $k$인 약수의 개수를 출력한다. 이 값은 매우 커질 수 있으므로 정확한 정수로 출력한다.