[Poi2010]Divine divisor

给定一个正整数 $n$ ，考虑其所有大于 $1$ 的因数。定义最大的整数 $k$ ，使得存在 $n$ 的因数 $d$ ，满足 $d^k$ 也是 $n$ 的因数。所有满足这一最大 $k$ 的因数 $d$ 都称为 $n$ 的非凡因子。

例如，当 $n=48$ 时，最大的 $k$ 为 $4$ ，因为 $2^4=16$ 是 $48$ 的因数，因此 $2$ 是一个非凡因子。

一个整数可能有多个非凡因子。例如，当 $n=6$ 时，最大的 $k$ 为 $1$ ，其非凡因子共有 $3$ 个，分别为 $2$ 、 $3$ 和 $6$ 。

现在给出 $m$ 个整数 $a_i$ ，令

n=\prod_{i=1}^{m}a_i。

请求出最大的 $k$ ，以及 $n$ 的非凡因子个数。

输入格式

输入共两行。

第一行包含一个整数 $m$ 。

第二行包含 $m$ 个以空格分隔的整数 $a_i$ ，这些整数的乘积为 $n$ 。

输出共两行。

第一行输出最大的整数 $k$ 。

第二行输出 $n$ 的非凡因子个数。

样例 $1$ ：

3
4 3 4

样例 $2$ ：

1
6

样例 $1$ ：

4
1

样例 $2$ ：

1
3

对于样例 $1$ ，有 $n=4\times 3\times 4=48$ 。最大的 $k$ 为 $4$ ，且唯一的非凡因子为 $2$ 。

本题为 POI 2010 试题「Divine divisor」，题面与测试数据整理自 BZOJ。

3
4 3 4

4
1

1
6

1
3