给定一个整数 $N > 1$。如果整数 $d > 1$ 满足 $d^k \mid N$ 且 $d^{k+1} \nmid N$，则称 $d$ 为 $N$ 的一个重数为 $k > 0$（$k$ 为整数）的约数。例如，$N=48=16 \times 3$，其约数包括：2（重数为 4）、3（重数为 1）、4（重数为 2）、6（重数为 1）等。

如果 $d$ 是 $N$ 的一个重数为 $k$ 的约数，且 $N$ 不存在重数大于 $k$ 的约数，则称 $d$ 为 $N$ 的“神圣约数”（divine divisor）。例如，$48$ 的唯一神圣约数是 2（重数为 4），而 $6$ 的神圣约数有 2、3 和 6（每个的重数均为 1）。

你的任务是确定 $N$ 的神圣约数的重数，以及 $N$ 的神圣约数的个数。

输入以一种不同寻常的方式给出。第一行包含一个整数 $n$ ($1 \le n \le 600$)。第二行包含 $n$ 个整数 $a_i$ ($2 \le a_i \le 10^{18}$)，它们之间用空格分隔。这些数表示 $N=a_1 \cdot a_2 \cdot \ldots \cdot a_n$。

第一行输出最大的整数 $k$，使得存在 $N$ 的约数 $d$ 满足 $d^k \mid N$。第二行输出一个整数 $D$，表示重数为 $k$ 的（神圣）约数的个数。

样例

输入格式 1

3
4 3 4

输出格式 1

4
1