题目背景

Mirko 的伟大的曾祖母 Katica 是一位狂热的数学家，她喜欢用数学游戏折磨她的曾孙。

题目描述

这一天，她在一张纸上写下了一个 $n$ 个数字的序列，并告知 Mirko 可以做如下操作若干次：

• 选取序列中的两个数字（我们不妨称之为 $A,B$），然后选取能整除 $A$ 的质数 $X$。之后，Mirko 把 $A$ 擦去并在原来的位置上写下 $\frac AX$，然后他把 $B$ 擦去并在原来的位置上写下 $B\times X$。

Mirko 希望得到最大分数，因为这样他可以从他的曾祖母那里得到糖果。一个包含 $n$ 个数字的序列的分数是这 $n$ 个数字的最大公因数。

Mirko 并不擅长这个，但又很想希望得到糖果，因此找到了你，希望你能编写一个程序计算最大的可能分数，同时他也希望你能够得出在得到最大可能的分数的前提下最少应当执行的操作数。

输入格式

输入共两行。

第一行一个整数 $n$，代表序列中的元素个数。
第二行包含 $n$ 个整数，描述 Katica 给 Mirko 的序列。

输出格式

输出仅一行两个整数，第一个整数表示 Mirko 最大能够得到的分数，第二个整数表示 Mirko 在能够获得最大的分数的前提下最少应当执行的操作数。

3
4 4 1

2 1

3
8 24 9

12 3

5
4 5 6 7 8

2 2

提示

【样例 1 解释】

对于样例 $1$，Mirko 可以选择序列中的 $4$ 和 $1$ 两个数，并选择 $4$ 的唯一质因子 $2$。之后 Mirko 将 $4$ 和 $1$ 擦去，并在它们原来所在的位置上都写下了 $2$，这样这个序列的分数是 $2$。可以证明这样的方案可以获得最大的分数并且在此前提下操作数最少。

【数据范围】

对于所有数据，$1\leqslant n\leqslant 100$，序列中的元素不超过 $10^6$。

【题目来源】

本题来源自 COCI 2009-2010 CONTEST 4 T3 IKS，按照原题数据配置，满分 $70$ 分。

由 Eason_AC 翻译整理提供。