[POI2010] NAJ-Divine Divisor

题目描述

An integer ![](http://main.edu.pl/images/OI17/naj-en-tex.1.png) is given. We say that an integer ![](http://main.edu.pl/images/OI17/naj-en-tex.2.png) is a divisor of ![](http://main.edu.pl/images/OI17/naj-en-tex.3.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.4.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.5.png) is integer) if ![](http://main.edu.pl/images/OI17/naj-en-tex.6.png) and ![](http://main.edu.pl/images/OI17/naj-en-tex.7.png) does not divide ![](http://main.edu.pl/images/OI17/naj-en-tex.8.png). For example, the number ![](http://main.edu.pl/images/OI17/naj-en-tex.9.png) has the following divisors: 2 with multiplicity 4, 3 with multiplicity 1, 4 with multiplicity 2, 6 with multiplicity 1, and so on. We say that a number ![](http://main.edu.pl/images/OI17/naj-en-tex.10.png) is a divine divisor of the number ![](http://main.edu.pl/images/OI17/naj-en-tex.11.png) if ![](http://main.edu.pl/images/OI17/naj-en-tex.12.png) is a divisor of ![](http://main.edu.pl/images/OI17/naj-en-tex.13.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.14.png) and ![](http://main.edu.pl/images/OI17/naj-en-tex.15.png) has no divisors with multiplicities greater than ![](http://main.edu.pl/images/OI17/naj-en-tex.16.png). For example, the sole divine divisor of 48 is 2 (with multiplicity 4), and the divine divisors of 6 are: 2, 3 and 6 (each with multiplicity 1). Your task is to determine the multiplicity of divine divisors of ![](http://main.edu.pl/images/OI17/naj-en-tex.17.png) and the number of its divine divisors. 给定一个正整数 $m$ 以及长度为 $m$ 的正整数序列 $a$ ,同时给出 $n = \prod_{i=1}^{m}{a_i}$。你需要找出一个最大的 $k$ 使得存在一个 $d$ , $d > 1$ 并且 $d^k | n$。求这个最大的 $k$ 以及在 $k$ 最大的情况下有多少个 $d$ 满足条件。

输入输出格式

输入格式


The number ![](http://main.edu.pl/images/OI17/naj-en-tex.18.png) is given on the standard input, though in a somewhat unusual way. The first line holds a single integer ![](http://main.edu.pl/images/OI17/naj-en-tex.19.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.20.png)). The second line holds ![](http://main.edu.pl/images/OI17/naj-en-tex.21.png) integers ![](http://main.edu.pl/images/OI17/naj-en-tex.22.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.23.png)) separated by single spaces. These denote that ![](http://main.edu.pl/images/OI17/naj-en-tex.24.png).

输出格式


The first line of the standard output should hold the maximum integer ![](http://main.edu.pl/images/OI17/naj-en-tex.25.png) such that there exists a divisor ![](http://main.edu.pl/images/OI17/naj-en-tex.26.png) of ![](http://main.edu.pl/images/OI17/naj-en-tex.27.png) such that ![](http://main.edu.pl/images/OI17/naj-en-tex.28.png). The second line should hold a single integer ![](http://main.edu.pl/images/OI17/naj-en-tex.29.png) that is the number of (divine) divisors of ![](http://main.edu.pl/images/OI17/naj-en-tex.30.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.31.png).

输入输出样例

输入样例 #1

3
4 3 4

输出样例 #1

4
1

说明

$1\le m\le 600$,且$\forall 1\le i\le m$,有$1\le a_i\le 10^{18}$