Title Description

There are $n$ positive integers $a [i]$, and their product is $p$. You can multiply $p$by a positive integer $q$, so that $p \times q$ is exactly the factorial of the positive integer $m$, and find the minimum value of $m$.

Input format

Two lines in total. The first line contains a positive integer $n$. The second line contains $n$positive integers $a[i]$.

Output format

There is one positive integer $m$ in each row.

Example

1
6

3

Data scale and agreement

For data of $10 \%$, $n \le 10$;

For data of $30 \%$, $n \le 1000$;

For data of $100 \%$, $n \le 100000, a [i] \le 100000$.