Divine Divisor

Memory limit: 64 MB

An integer is given. We say that an integer is a divisor of with multiplicity ( is integer) if and does not divide . For example, the number 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 is a divine divisor of the number if is a divisor of with multiplicity and has no divisors with multiplicities greater than . 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 and the number of its divine divisors.

Input

The number is given on the standard input, though in a somewhat unusual way. The first line holds a single integer (). The second line holds integers () separated by single spaces. These denote that .

Output

The first line of the standard output should hold the maximum integer such that there exists a divisor of such that . The second line should hold a single integer that is the number of (divine) divisors of with multiplicity .

Example

For the input data:

3
4 3 4

the correct result is:

4
1

whereas for the input:

1
6

the correct result is:

1
3

Grading

Should your program print out the correct multiplicity of a divine divisor of , but fail to print in the second line the correct number of divine divisors of (or fail to print that number at all), it will be awarded 50% of the score for that particular test, scaled accordingly if it exceeds half the time limit.

Task author: Jakub Radoszewski.