#2082. [Poi2010]Divine divisor

内存限制:259 MiB 时间限制:30 Sec

题目描述

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

输入格式

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

输出格式

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

样例

样例输入


			
【样例输入1】
3
4 3 4 (n=4*3*4=48)
【样例输入2】
1
6

样例输出


			
【样例输出1】
4 (k最大为4)
1 (一个非凡因子,2)
【样例输出2】
1
3

数据范围与提示