题目描述

小 C 的曾祖母会和他做一个数学游戏，规则如下：

• 初始条件：有一个包含 $N$ 个正整数的序列。

• 允许操作：选择序列中任意两个位置的数（记为 $A$、$B$），执行以下步骤：

  1. 取 $A$ 的一个质因子 $X$；
  2. 将 $A$ 替换为 $A/X$；
  3. 将 $B$ 替换为 $B\times X$。

可以进行任意次上述操作，但需要满足两个目标：

1. 使序列中 $N$ 个元素的最大公约数（GCD）尽可能大；
2. 在满足目标 $1$ 的前提下，使用最少的操作次数。

请计算最终能得到的最大公约数的最大值，以及对应的最少操作次数。

输入格式

• 第一行：一个正整数 $N$（$1\le N\le 100$），表示序列长度。

• 第二行：$N$ 个正整数，表示序列中的元素。每个元素不超过 $10^6$。

输出格式

输出一行，包含两个正整数（用空格分隔）：

• 第一个数：能达到的最大公约数的最大值；
• 第二个数：在达到该最大公约数时所需的最少操作次数。

样例输入 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