Mirko 的曾祖母 Katica 是一位狂热的数学家。她喜欢用数学游戏来折磨 Mirko。这一次，她在纸上写下了一个数列，并告诉 Mirko 他可以进行以下操作：

• 选择数列中的任意两个数（我们称之为 $A$ 和 $B$）以及一个质数 $X$，使得 $A$ 能被 $X$ 整除。然后，Mirko 擦掉 $A$ 并在其位置写上 $\frac{A}{X}$。最后，他擦掉 $B$ 并在其位置写上 $B \times X$。

Mirko 可以进行任意多次该操作。他的目标是获得尽可能高的分数，因为如果他做到了，他就能从曾祖母那里得到糖果。一个数列的分数是该数列中所有数的最大公约数。

他不太擅长这个，但他很想吃糖果，所以他请求你帮助他。写一个程序，计算出可能获得的最大分数。既然你人很好，你还应该输出 Mirko 为了获得最大可能分数所需进行的最少操作次数。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 100$），表示初始数列中元素的个数。

输入的第二行包含 $N$ 个小于或等于 $1\,000\,000$ 的正整数，表示 Katica 给 Mirko 的数列。

输出格式

输出仅一行，包含两个整数。第一个整数是 Mirko 可以获得的最大可能分数。第二个整数是获得该分数所需的最少操作次数。

样例

输入样例 1

3
4 4 1

输出样例 1

2 1

输入样例 2

3
8 24 9

输出样例 2

12 3

输入样例 3

5
4 5 6 7 8

输出样例 3

2 2