Description

Tz耍畸形，在寂寞的时候玩一个游戏，他随便找出一个n，然后算出n的所有因子，最后找出一个最大的k，即有一个因子d的k次方为n的因子，那个因子d就是非凡因子啦 。比如48他的非凡因子d就是2，k最大为4，因为16也是48的因子。一个整数的非凡因子可能不止一个，比如6就有3个：2，3，6（k最大是1）。

Format

Input

有两行，第一行给出一个整数m(1<=m<=600)，第二行是由空格分开的m个数ai(2<=ai<=1018(10的18次方))，n就是ai的乘积（n=a1a2a3*....*am）。

Output

也有两行（Tz真畸形），第一行为最大的k，第二行为非凡因子d的个数。

Samples

3
4 3 4 （n=4*3*4=48）

1
6

4 （k最大为4）
1 （一个非凡因子，2）

1
3